DNA Computing in de praktijk

DNA Computing in de praktijk

S.D. Anoep V.R. Badal

V.R.K. Boedhram

S.P. Rangoe D.J. Strijdhaftig

F.S.D. van der Werf Abstract In dit artikel wordt de praktische toepasbaarheid van DNA computing onderzocht. Hiertoe wordt eerst een korte introductie gegeven tot DNA computing en vervolgens worden twee algemene toepassingsgebieden beschreven, te weten informatieopslag en parallelle verwerking. Deze worden gevolgd door twee specifieke toepassingen, cryptografie en signaalverwerking. Concluderend wordt gesteld dat DNA computing nog niet praktisch toepasbaar is, zolang er nog geen vorderingen in de biochemie worden gemaakt met betrekking tot de snelheid van DNA operaties.

1. Inleiding In de informatica zijn veel problemen bekend die niet in polynomiale tijd opgelost kunnen worden. In de zoektocht naar oplossing met een doenlijk tijdsbestek, is men beland op een biologisch spoor. De moleculaire biologie wordt nu gebruikt om oplossingen voor problemen uit de informatica te genereren. Hiervoor kan DNA worden gebruikt en vandaar dat deze methode DNA computing genoemd wordt. In 1994 ontdekte Adleman een methode om met behulp van DNA het Hamiltoons pad probleem op te lossen [1]. Sindsdien is er veel onderzoek gedaan naar de mogelijkheden van DNA met betrekking tot calculaties. In dit artikel komt de praktische toepasbaarheid van DNA computing aan bod. DNA computing wordt toegepast als oplossingsmethode voor ondoenlijke problemen, maar kan ook voor andere toepassingsgebieden worden gebruikt. Om een goed begrip te krijgen van DNA computing, wordt eerst een algemene inleiding over DNA gegeven. Hierna komt informatieopslag aan bod, omdat dit een essentieel onderdeel is van de informatica. Deze informatie moet verwerkt kunnen worden en het liefst op een zo efficiënt mogelijke manier. DNA computing biedt de mogelijkheid om deze informatie parallel te verwerken. In het hoofdstuk over parallelle processing zal hierop dieper worden ingegaan. Met behulp van deze twee fundamenten kunnen praktische toepassingen gerealiseerd worden, zoals cryptografie en signaalverwerking. Vervolgens worden deze twee toepassingen beschreven, omdat bij deze toepassingen informatieopslag en parallelle verwerking in DNA computing goed gebruikt kunnen worden. Bij de behandeling van cryptografie komen zowel encryptie als het kraken van encryptiemethoden aan de orde. Tot slot wordt digitale signaalverwerking behandeld. Ter afsluiting van het artikel wordt er een conclusie getrokken aangaande de praktische toepasbaarheid en haalbaarheid van het gebruik van DNA op de verschillende toepassingsgebieden.

2. DNA Computing Voordat ingegaan wordt op het gebruik van DNA als berekeningsmiddel en het gebruik hiervan op de verschillende toepassingsgebieden, moeten we een goed beeld krijgen van de structuur van DNA zelf.

2.1.

Wat is DNA?

DNA (desoxyribonucleïnezuur) bevat de complete erfelijke informatie van een organisme. Hierin liggen uiterlijke kenmerken, zoals oog- en haarkleur, vast. Elk DNA molecule bestaat uit twee complementaire strengen die op hun beurt uit vier verschillende nucleotiden bestaan, ook wel basen genoemd: adenine, thymine, cytosine en guanine. Deze vier basen zullen in het vervolg worden aangeduid met de letters: A, T, C en G. De twee strengen zijn op een zodanige manier met elkaar verbonden dat zij een dubbele helix, de chemische structuur van DNA, vormen. Zij worden bij elkaar gehouden door waterstofbruggen, die slechts voorkomen bij complementaire basenparen. Deze zijn ook wel bekend als Watson-Crick complementen, die enerzijds gevormd worden door A en T en anderzijds door C en G. Elke nucleotide heeft twee uiteinden, waarvan één een fosfaatgroep en de ander een hydroxidegroep bevat. De fosfaatgroep staat ook wel bekend als 5’, terwijl de hydroxidegroep wordt aangeduid als 3’. Bovendien zijn deze twee groepen complementen van elkaar, zoals de nucleotiden, die de Watson-Crick complementen vormen. Wanneer nucleotiden samengebracht worden om een keten te vormen wordt het ene uiteinde van de ene nucleotide verbonden aan het complementaire uiteinde van een andere nucleotide [3]. Daarom kunnen we de opeenvolging van basen in zulke ketens beschouwen alsof zij geordend zijn. Deze ordening speelt een belangrijke rol, omdat zij beperkingen legt op het uitvoeren van operaties op de strengen. DNA ketens zouden niet bruikbaar zijn als deze niet te manipuleren waren. Dit is mogelijk met behulp van enzymen, die een reactie aangaan en vervolgens het gewenste resultaat leveren. Een aantal van deze operaties zal beschreven worden in de volgende sectie.

2.2.

Operaties op DNA

Hierboven is gesproken over de operaties die op DNA kunnen worden uitgevoerd. Er bestaan veel van deze operaties, maar in dit gedeelte zullen slechts die operaties worden behandeld, die in de rest van het artikel ook toegepast worden [9, 17]. •

• • •

• •

•

Synthese: een DNA keten wordt stap voor stap opgebouwd uit nucleotiden. Zo wordt om de keten ACT te vormen de nucleotide A als basis gebruikt. De A basen worden vergoten met een oplossing van C basen. De reactie die volgt creëert de keten AC. De overgebleven reactie vloeistof wordt afgevoerd waarna de AC ketens worden overgoten met T basen. Het eindresultaat is de keten ACT. Ontharden: door de temperatuur te verlagen kunnen twee complementaire DNA strengen worden samengevoegd tot een helix. Smelten: door de temperatuur te verhogen kan een DNA helix worden gesplitst in twee complementaire DNA strengen. Amplificatie: door een DNA oplossing achtereenvolgens te verwarmen en af te koelen wordt een helix gesplitst en weer samengevoegd. Door dit proces uit te voeren in een oplossing van basen hechten de vrije basen zich bij het afkoelen aan de complementaire strengen waardoor er in plaats van één helix, twee helices worden gevormd. Elke keer dat dit proces wordt uitgevoerd wordt het aantal DNA strengen verdubbeld. Detecteer: nagaan of in een DNA oplossing een bepaalde DNA streng tenminste één keer voorkomt. Extractie: het extraheren van DNA strengen die een bepaalde substreng bevatten. Lengte: het extraheren van DNA strengen met een bepaalde lengte.

2.3.

Het ontstaan van DNA computing

Nu er voldoende achtergrondinformatie over de structuur van DNA en de operaties hierop uiteen is gezet, kan overgegaan worden op de ontwikkeling van DNA computing. In de afgelopen jaren zijn er verscheidene nieuwe ideeën ontwikkeld om niet-elektronische natuurlijke verschijnselen te gebruiken voor efficiënte berekeningen. In de klassieke, op elektronica gebaseerde berekeningen wordt informatie per bit opgeslagen en gewijzigd door elektrische en elektromagnetische middelen. Het aantal stappen dat per tijdseenheid doorlopen wordt, is zeer groot, maar het aantal processors dat parallel kan draaien is klein. Het hoofddoel van de eerdergenoemde nieuwe ideeën was niet het aantal stappen per tijdseenheid te vergroten, maar het aantal processors dat parallel kon draaien te verhogen. In 1994 kwamen verschillende benaderingen op gang die gebruik maakten van de biologische eigenschappen van DNA ketens om informatie op te slaan en te wijzigen. Het algemene idee is om een groot aantal DNA ketens als parallel draaiende processors te gebruiken, zo kwam DNA computing tot stand [17, 21]. Adleman was de eerste, die de berekeningskracht van DNA ter sprake bracht. Dit deed hij door enkele instanties van het Hamiltoons pad probleem op te lossen door middel van biologische experimenten met DNA strengen [1, 17]. Adleman was ruim een week bezig met dit experiment, wat heel ontmoedigend lijkt, maar het grote voordeel is dat het aantal operaties slechts lineair groeit met het aantal knopen van de graaf. Dit is verreweg het meest efficiënte algoritme om dit probleem op te lossen, aangezien er geen deterministisch polynomiaal algoritme bekend is voor het oplossen van dit probleem. Lipton breidde het werk van Adleman uit, zodat het de mogelijkheid bood om elk NP probleem in polynomiale tijd op te lossen [21] en bracht de praktische relevantie van deze benadering op gang. Hij stelde een biologisch berekeningsmodel op, dat naast de klassieke elementen, ook grote verzamelingen van DNA ketens kon manipuleren. Dit hield in dat er operaties werden uitgevoerd op elke DNA keten in een reageerbuis. Op deze wijze correspondeerde elke DNA keten met een hoeveelheid aan informatie en al deze hoeveelheden zouden parallel verwerkt kunnen worden. In 1995 werd DNA computing nog populairder: het SAT probleem werd opgelost met een nieuw en praktischer algoritme [12]. Ook werd eraan gedacht DNA nu te gebruiken als geheugen, waarover meer te vinden is in het volgende hoofdstuk. Adleman zelf was degene die het geheugenmodel presenteerde. Donald Beaver stelde voor om DNA te gebruiken om grote getallen te ontbinden in factoren. Dit is een relevant probleem in vele cryptografische toepassingen, die ter sprake komen in het hierop betrekking hebbende hoofdstuk. Bovendien was hij degene die een Turing machine ontwierp met behulp van een enkele DNA keten. Na deze ontwikkelingen nam de populariteit van DNA computing immens toe. Vele onderzoeken werden gedaan en ook werden er vele artikelen over dit onderwerp gepubliceerd.

3. Informatieopslag Nu het aspect van DNA duidelijk naar voren is gebracht, zal informatieopslag met DNA computing worden behandeld en wordt aangegeven of dit een verbetering is in vergelijking met de huidige opslagmethoden. Dit hoofdstuk bespreekt de mogelijkheid om informatie in DNA reeksen op te slaan. Vervolgens worden de voor- en nadelen, die kleven aan het gebruik van DNA als informatiemedium, besproken.

3.1.

DNA en dataopslag

In de huidige informatiemaatschappij is informatiebehoud van cruciaal belang. Elke dag groeit de hoeveelheid informatie. Jarenlang wist men de grenzen van de transistor te verleggen, maar

de dag dat dit niet meer zal lukken is niet ver meer. Daarom wordt men gedreven om nieuwe manieren te vinden om informatie op te slaan.

3.1.1.

Associatief geheugen

Baum beschrijft in zijn artikel de mogelijkheid om DNA te gebruiken als associatief geheugen [2]. Het geheugen is in feite een vat met DNA moleculen. Twee verschillende DNA reeksen worden gebruikt om een 0 en een 1 te coderen. Een woord bestaat dan uit een samenstelling van deze subreeksen. Een geheugen is nutteloos als er geen lees- en schrijfoperaties kunnen worden uitgevoerd. Omdat het geheugen associatief is, is voor een leesoperatie een subreeks van het te lezen woord nodig. Met behulp van extractie, beschreven in het vorige hoofdstuk, kunnen alle DNA moleculen met een bepaalde subreeks worden gescheiden van de DNA moleculen die deze subreeks niet bevatten. Nadat de DNA moleculen met de subreeks zijn gescheiden kan men van die moleculen het complete woord lezen. Na een leesoperatie moeten de DNA moleculen, die uit het geheugen zijn gehaald, weer terug in het geheugen worden geplaatst. Het is eenvoudiger om voor de leesoperatie met behulp van amplificatie eerst een kopie te maken van het geheugen en na de leesoperatie het geheugen te vervangen door de kopie. Schrijfoperaties gebeuren door het toevoegen van het woord aan het geheugen. Het woord kan met behulp van de synthese worden gecreëerd. Het nieuwe woord wordt dan fysiek toegevoegd aan het geheugen, dat wil zeggen het vat met DNA. Het verwijderen van woorden gebeurt door middel van extractie. Door de DNA reeksen logisch op te delen in een adresgedeelte en een datagedeelte, kan DNA worden gebruikt als random access memory. Om het datagedeelte terug te krijgen moet het volledige adresgedeelte worden meegegeven. Als een bepaald adres al eerder is beschreven, moet een volgende schrijfoperatie op dat adres door een verwijderoperatie worden voorgegaan. Als dit niet wordt gedaan bevat het geheugen twee verschillende waarden voor één geheugenlocatie. Het geheugen is dan onbruikbaar. Er zijn ook andere manieren om met DNA data op te slaan. Zo maakt het Sticker model [17] gebruik van twee soorten DNA strengen: geheugenstrengen en stickers. Geheugenstrengen bestaan uit meerdere regionen en representeren binaire strings. Stickers zijn de Watson-Crick complementen van de regionen van geheugenstrengen. Als van een bepaalde regio de bijbehorende sticker aanwezig is, betekent dit dat het geassocieerde bit op 1 gesteld is, terwijl afwezigheid van de sticker het bit op 0 stelt. Door de aan- of afwezigheid van stickers wordt een geheugenstreng geheel of gedeeltelijk tot een helix gevormd. Zo een geheugenstreng dat geheel of gedeeltelijk een helix is, heet een complex. Een complex met k regionen representeert dus een string met k bits.

3.1.2.

Relationele Databases

Experimenten hebben aangetoond dat het in de praktijk zelfs mogelijk is om grootschalige databases in DNA [20] te implementeren. Daarbij was het mogelijk om associatief door de database te zoeken. Katsányi neemt dit nog een stap verder [10]. Katsányi geeft een mogelijke implementatie in chemische reacties van queries op relationele DNA databases. Met behulp van deze implementaties is het mogelijk om queries op DNA databases uit te voeren zoals op ‘normale’ databases. Operaties zoals vereniging, doorsnede, cartesisch product, projectie en verschil zijn dan mogelijk.

3.1.3.

Databescherming

DNA reeksen zijn erg gevoelig voor invloeden van buiten af: een los DNA molecule kan eenvoudig worden vernietigd door ongunstige omstandigheden [27], zoals extreme temperaturen en straling. Als DNA onder de juiste omstandigheden wordt bewaard, is deze

gevoeligheid geen probleem. Voor sommige toepassingen van geheugen echter is dat niet mogelijk. Een oplossing hiervoor is om het DNA te injecteren in een levend organisme dat onder extreme omstandigheden overleeft. De informatie wordt dan samengevoegd met het DNA van het organisme zelf. Zodra het organisme sterft gaat ook de informatie verloren. Om informatiebehoud te verzekeren moet het organisme zich om die reden vermenigvuldigen en daarbij de informatie doorgeven. Onderzoek heeft uitgewezen dat de bacterie Deinococcus een uitstekende kandidaat is [27]. Deze bacterie is bestand tegen extreme omstandigheden zoals extreme temperaturen, ultraviolette en ioniserende straling. Het DNA van deze bacterie is volledig bekend. De informatie moet dusdanig worden gecodeerd dat de DNA reeksen niet voorkomen in het DNA van het organisme zelf, om ongewenste mutaties te voorkomen. Een probleem is dat de bacterie de informatie gaat interpreteren als genetische code. Om dit te voorkomen worden speciale DNA reeksen gebruikt die de bacterie vertellen dat op dat punt de genetische code stopt. De bacterie zal dan de rest van DNA reeks negeren.

3.2.

Voordelen

Het grote voordeel van dataopslag met behulp van DNA is de enorme opslagdichtheid. Theoretisch kan 1 gram DNA ongeveer 4.2 x 1021 bits opslaan, terwijl een conventioneel geheugen ‘slechts’ 109 bits per gram kan opslaan [20] en een liter water met DNA 108 terabytes [10]. Baum vindt vaten met DNA die evenveel informatie als de menselijke hersenen kunnen opslaan niet ondenkbaar [2]. Een ander groot voordeel is dat het zoeken door DNA databases met constante tijd kan worden uitgevoerd [10]. Huidige database-implementaties gebaseerd op de elektrische computer kunnen dit niet evenaren. Naarmate de database meer informatie bevat duurt het zoeken langer. Door de informatie te injecteren in organismen kan deze informatie de meeste extreme omstandigheden overleven. De bacterie zal zich vermenigvuldigen, dus als één bacterie sterft maakt dat niet uit, er zijn dan nog veel andere bacteriën die de juiste informatie dragen.

3.3.

Nadelen

DNA geheugen is gebaseerd op chemische reacties. Dit brengt een bepaalde mate van onzekerheid in het spel. Men kan er nooit 100 procent zeker van zijn dat een bepaalde chemische reactie daadwerkelijk zal plaatsvinden. Dat reagerende moleculen daadwerkelijk met elkaar ‘botsen’, is nooit te voorspellen. Door grote hoeveelheden te gebruiken kan de fout wel erg klein worden gemaakt, maar volledige zekerheid is niet mogelijk. Zoals vermeld kan de informatie ter bescherming bij organismen worden geïnjecteerd. Bij vermenigvuldiging is echter niet uitgesloten dat er mutaties kunnen plaatsvinden. Dit zou de integriteit van de informatie aan kunnen tasten. De gekozen bacterie heeft wel een laag mutatiegehalte, maar het is niet uitgesloten. Daarnaast is het mogelijk een checksum aan de informatie toe te voegen om integriteit te controleren. De toegankelijkheid van het DNA geheugen is zeer slecht in vergelijking met huidige geheugens. Geheugens gebaseerd op transistors kunnen lees- en schrijfoperaties in microseconden uitvoeren. Bij DNA liggen toegangstijden in orde van uren [2].

4. Parallelle operaties met behulp van DNA computing Nu informatie in DNA opgeslagen kan worden, wordt ingegaan op de potentie van DNA als essentieel onderdeel van een parallelle computer. Onderzoek hiernaar is gericht op het maken van parallelle modellen, die uitgevoerd kunnen worden met op DNA gebaseerde chemische

processen en het ontwikkelen van algoritmen hiervoor. Biologische macromoleculen kunnen gebruikt worden voor het opslaan van informatie in deze parallelle computers [14].

4.1.

Parallelle biologische machines

Biochemische reacties kunnen gebruikt worden om algoritmen op te lossen. Wetend dat een vast aantal biochemische reacties tegelijkertijd kan plaatsvinden, kunnen er dus miljoenen parallelle berekeningen uitgevoerd worden [8]. Methoden voor het oplossen van verschillende NP complete problemen zijn voorgesteld en uitgevoerd op kleine schaal. Het is echter de vraag of deze algoritmen makkelijk te ontwikkelen en te implementeren zijn en of deze wel optimaal gebruik maken van het parallelle aspect van DNA computing.

4.1.1.

DNA keten als basis

Voor het realiseren van een biologische computer moet men een parallelle machine construeren waarbij iedere fase die een processor kan aannemen gecodeerd is als een DNA keten. De bewerkingen kunnen dan vervolgens tegelijkertijd worden uitgevoerd op alle DNA moleculen. Deze worden gebruikt voor het uitvoeren van parallelle lokale lees- en/of schrijfoperaties van het geheugen, logische operaties en de basiseigenschappen, zoals wiskundige berekeningen.

4.1.2.

Hoge graad van parallellisme

Het rekenvermogen wordt bepaald door de tijd dat een instructie plaatsvindt en de graad van het parallellisme. De duur van een biologische operatiestap is ongeveer 100 seconden. Dit is dus aanzienlijk langer dan een instructie uitgevoerd op een elektronische computer. Aangezien een biologische computer (1026 moleculen) een hogere graad heeft dan een elektronische computer (105 processoren) is een biologische computer in theorie veel krachtiger. Het geschatte aantal instructies dat parallel uitgevoerd kan worden op een biologische computer is 1024, dit is gelijk aan 634.195 computers die van 1945 tot 1995 miljarden instructies per seconde uitvoerden [11]. Wat de onderzoekers dus motiveert is de gedachte dat deze vorm van parallellisme problemen kan oplossen, die niet oplosbaar zijn met de huidige elektronische computers.

4.1.3.

Parallelle rekenkunde

In de traditionele DNA computing wordt aan de hand van de uitvoer teruggewerkt naar de invoer; uit alle mogelijke oplossingen wordt dan de correcte geselecteerd. Deze aanpak is prima voor het oplossen van combinatorische problemen, echter voor het bouwen van een breed inzetbare DNA computer is het nodig om mathematische operaties uit te kunnen voeren. Het wordt dan nodig om vanuit de invoer te werken naar het correcte resultaat. Guarnieri, Fliss en Bancroft [6] zijn erin geslaagd om een op DNA gebaseerd optelalgoritme te implementeren. Om positieve binaire getallen op te tellen moet een toegepaste codering in staat zijn om van elk bit informatie over de waarde, de positie en de carry te coderen. Een getal wordt daarom gecodeerd door DNA strengen die elk kunnen worden opgedeeld in drie delen namelijk een deel voor de carry, een deel voor de binaire waarde en een deel voor de operator. De optelling van 2 bit integers geschiedt in twee fasen: 1 Het genereren van DNA representaties van alle 2 bit integers. 2 Het uitvoeren van de horizontale kettingreactie. De horizontale kettingreactie houdt het volgende in: de 2 bit integers kunnen paarsgewijs worden opgeteld. Het optellen van een paar gebeurt in vier stappen. Bij elke stap worden bepaalde complementen gekoppeld om een nieuwe langere streng te vormen welke uiteindelijk het eindresultaat representeert. Volgens Guarnieri et al. werden experimenten van 1+1, 1+0, 0+1 en 0+0 met succes uitgevoerd [6].

Een nadeel bij deze methode is dat de uitkomst een andere vorm heeft dan de invoer waardoor het nog niet mogelijk is om verder te tellen met een verkregen eindresultaat. Nog een nadeel is dat het werk minstens twee dagen in beslag neemt. Relatief weinig werk in DNA computing, maar wel extreem veel vergeleken met traditionele computing. Om te concurreren met het gebruikelijke silicium, is het belangrijk dat een biologische machine snel basisoperaties kan uitvoeren. Traditionele computers kunnen namelijk rekenkundige en booleaanse operaties in enkele stappen uitvoeren. Guarnieri en Bancroft hebben een basis gelegd in het sommeren maar doordat hun algoritme slechts twee getallen per keer kon optellen en geen herhaaldelijke operaties kon uitvoeren werd bij het massieve parallelle aspect tekort geschoten. Vervolgens kwamen er nog verscheidene algoritmen voor het oplossen van dit rekenkundige probleem. Totdat Rubin et al. een demonstratie gaven van experimentele sequentiële rekenoperaties. Dit had als gevolg dat ook omkeerbare rekenoperaties konden worden uitgevoerd [19]. Hoewel het gebruikelijk is om aritmetische en booleaanse operaties uit te voeren op numerieke en booleaanse data zal parallele rekenkunde ons instaat stellen om op hele verzamelingen operaties uit te voeren.

4.1.4.

Versnelling van operaties

Beaver, Reif, en Papadimitrion [19] hebben onafhankelijk van elkaar bewezen dat elke sequentiële operatie, die gebonden is aan een lineaire ruimte exponentieel versneld kan worden. Ze toonden aan dat een sequentiële Turing machine berekeningen met ruimte s in tijd O(s) kon simuleren.

4.2.

Voordelen

Biologische machines hebben ten opzichte van de huidige supercomputers vele positieve aspecten. Zo is duidelijk geworden dat ze een veel hogere graad van parallellisme kunnen aannemen. Dit is een doorbraak voor het oplossen van uitermate complexe problemen, die bijvoorbeeld niet met huidige supercomputers opgelost kunnen worden óf zo lang duren dat ze niet haalbaar zijn. Een ander duidelijk aantoonbaar voordeel is het efficiënte energieverbruik. Adleman toonde aan dat er naar schatting 2 x 1019 molecule operaties kunnen plaatsvinden per Joule. In verhouding met de huidige supercomputers waarbij op zijn hoogst 109 operaties per Joule kunnen plaatsvinden, is dit dus extreem zuinig. Uit het voorgaande hoofdstuk is de opslag, die haalbaar is binnen een processor van een biologische machine, zeer opmerkelijk te noemen. Zo kan bij het opslaan van gegevens in DNA moleculen de dichtheid toenemen tot ongeveer 1 bit per kubieke nanometer. Huidige opslagmedia, zoals een videotape, bevatten informatie met een dichtheid van ongeveer 1 bit per 1012 nanometer. In het hoofdstuk van informatieopslag werd hierop dieper ingegaan.

4.3.

Nadelen

Het probleem van parallelle rekenkunde is dat het nog niet ontwikkeld is, terwijl de basis al wel is gelegd. Zo moeten er bijvoorbeeld algoritmen komen die het parallelle aspect van een biologische machine nog beter kunnen benutten. Het is tot nu toe alleen nog maar gelukt om een fractie van de totale graad van parallellisme te verkrijgen. Een aspect dat ook hierbij komt kijken, is dat het lastig is voor ontwikkelaars om een biologische machine te ontwikkelen en te implementeren. Het totale systeem is veel te complex hiervoor, waardoor er met veel dingen rekening gehouden moet worden. Bovendien liggen de productiekosten van de gebruikte hardware hoog, want de hoeveelheid DNA die nodig is om een proces uit te voeren kan zelfs oplopen tot het totale gewicht van de Aarde [1, 17].

5. Cryptografie DNA computing brengt nieuwe mogelijkheden voor de cryptografie met zich mee. Zoals beschreven in voorgaande hoofdstukken zijn parallelle verwerking en geheugen voordelen van DNA computing. Dit, gecombineerd met de willekeurige aard van DNA strengen, kan gebruikt worden om te experimenteren met nieuwe en bestaande encryptiemethoden of om bestaande methoden te kraken. De beveiliging van data door middel van cryptografie is door de jaren heen steeds belangrijker geworden. Dit heeft te maken met het sterk toenemende communicatieverkeer, evenals de aard van de communicatie. Er blijkt een sterke vraag te zijn naar vertrouwelijk dataverkeer en identificatie van personen dan wel computers. Doordat er steeds grotere hoeveelheden data versleuteld moeten worden, is snelheid van de encryptiemethoden van belang. Dit hoofdstuk zal twee methoden beschrijven voor encryptie door middel van DNA computing evenals een methode om een bestaande encryptiemethode te kraken. Hiertoe wordt eerst in de volgende sectie een inleiding gegeven tot deze methoden, die zijn geïmplementeerd in conventionele computers. Vervolgens wordt beschreven hoe DNA computing hiervoor ook gebruikt kan worden, om af te sluiten met een discussie over de praktische toepasbaarheid van DNA cryptografie.

5.1.

Introductie tot cryptografie

Data, die gelezen en begrepen kan worden zonder speciale middelen, wordt plaintext genoemd. Met encryptie wordt deze plaintext geconverteerd met behulp van een sleutel naar onbegrijpelijke ciphertext. De omgekeerde operatie, van ciphertext naar plaintext, wordt decryptie genoemd. Encryptie kan opgedeeld worden in twee gebieden, te weten conventionele encryptie en public key encryptie. Bij conventionele encryptie wordt één sleutel gebruikt voor de encryptie en decryptie van een bericht. De Data Encryption Standard (DES) is een bekend voorbeeld van een conventionele encryptiemethode. Een probleem bij conventionele encryptie is de distributie van de sleutel. Omdat zender en ontvanger de geheime sleutel nodig hebben, is er een vorm van transport nodig. Bij onderschepping van deze sleutel is de hele encryptie nutteloos. Public key encryptie lost dit probleem op door verschillende sleutels te gebruiken voor encryptie en decryptie. In dit artikel zal niet worden ingegaan op public key encryptie. Encryptiemethoden kunnen tevens opgedeeld worden in drie andere categorieën: substitutie ciphers, transpositie ciphers en one-time pads. Substitutie ciphers vervangen elke letter in de plaintext door een andere letter om deze te verbergen. Eén van de oudste en bekendste substitutie ciphers is de Caesar cipher waarbij de a een D wordt, de b een E, de c een F en de z een C. Er zijn vele varianten hierop mogelijk zoals het gebruik van verschillende alfabetten voor substitutie of het vervangen van één letter door een lettergroep. Transpositie ciphers vervangen de letters in de plaintext niet, zij veranderen slechts de volgorde van de letters om het bericht te verbergen [22].

5.2.

Cryptografie door middel van DNA computing

In deze sectie worden twee encryptiemethoden besproken, en hoe deze geïmplementeerd kunnen worden in DNA. Ook zal een methode gegeven worden om een bestaande encryptiemethode te kraken met DNA computing.

5.2.1.

Steganografie met DNA

Steganografie is het verbergen van geheime berichten in andere onbelangrijke informatie, en wordt als een simpele vorm van cryptografie beschouwd. Het komt voort uit een

spionagetechniek uit de Tweede Wereldoorlog waarbij een verkleinde foto op de punten in een brief geplakt werd. In het hoofdstuk over informatieopslag met DNA werd geschat dat een liter water met DNA ongeveer 108 terabytes aan informatie kan opslaan. Door hierin een geheim bericht van enkele megabytes te verstoppen, is het ondoenlijk het bericht te ontdekken zonder kennis van de plaats. Clelland et. al hebben in een paper dit idee uitgewerkt [4]. Zij hebben uit de doeken gedaan hoe steganografie mogelijk is door berichten gecodeerd als DNA strengen te verbergen door ze in een grote hoeveelheid DNA te verstoppen. Zij gebruikten hierbij een substitutie cipher waarbij elk uniek tripel basen een letter van het alfabet werd toegewezen. Het begin en eind van het geheime bericht werd aangegeven door speciale reeksen basenparen. De ontvanger kent deze reeksen en kan de juiste enzymen gebruiken om het bericht te amplificeren en uiteindelijk te extraheren. Doordat kleine hoeveelheden DNA extreem veel basenparen bevatten is het voor een onderschepper ondoenlijk om de plaats van het bericht te ontdekken zonder kennis van de speciale reeksen basenparen. Deze methode blijkt ook zeer robuust te zijn, Clelland et. al hebben namelijk een experiment uitgevoerd waarbij een geheim bericht volgens bovenstaande procedure in ongeveer 100 nucleotiden gecodeerd werd. Vervolgens heeft hij het DNA (met bericht) op de punten van een geprinte brief gepipetteerd en deze brieven verstuurd via de post. Na ontvangst was het mogelijk om het geheime bericht geheel correct te decoderen door amplificatie en extractie [4].

5.2.2.

DNA One-time pads

Tot nu toe is er slechts één onbreekbare encryptiemethode bekend, namelijk de zogenoemde one-time pads. Het is in feite een substitutie cipher waarbij een willekeurige bitreeks als sleutel wordt gebruikt. De bitreeks is van dezelfde grootte als de te versleutelen data. Om de encryptie tot stand te brengen wordt de plaintext eerst geconverteerd naar een bitreeks. Vervolgens wordt de ciphertext verkregen door bit voor bit de booleaanse XOR-operatie uit te voeren op de sleutel en de plaintext [22]. De kracht van deze methode zit in het feit dat de ciphertext geen enkele informatie bevat die decryptie mogelijk kan maken zonder kennis van de gebruikte sleutel. Het grote nadeel van deze methode is dat de sleutel even lang moet zijn als de plaintext. Dit kan voor problemen zorgen bij encryptie van grote hoeveelheden data zoals videobestanden. Een ander nadeel is dat dezelfde sleutel bekend moet zijn bij zowel ontvanger als zender [22]. DNA heeft een aantal karakteristieken die het mogelijk maken om one-time pads te gebruiken. DNA strengen hebben namelijk van nature een willekeurige samenstelling. Het is zeer eenvoudig om een DNA streng te verkrijgen met volstrekt willekeurige basenparen. Een andere eigenschap is de capaciteit van informatieopslag van DNA strengen. Deze twee eigenschappen maken DNA zeer geschikt voor het construeren van sleutels voor one-time pads. Gehani et al. hebben beschreven hoe het mogelijk is om DNA computing te gebruiken om data te versleutelen door middel van one-time pads. Er zijn hierbij drie stappen nodig: het coderen van de sleutel en plaintext in DNA, het genereren van de sleutel en het implementeren van de booleaanse XOR-operatie in DNA operaties [5]. Voor de codering van de plaintext en het generen van de one-time pads in DNA wordt gekozen voor DNA tiles, complexen van meerdere DNA strengen. Deze tiles worden gebruikt omdat er parallelle XOR-operaties voor bekend zijn en omdat deze zelfassemblerend zijn, wat het genereren van de sleutel mogelijk maakt [5].

5.2.3.

DES kraken met de DNA computer

Behalve het construeren van sterke encryptie met DNA computing, kan deze vorm van computing ook gebruikt worden om bestaande encryptiemethoden te kraken. Met het kraken

van een encryptiemethode zoals DES wordt bedoeld het ontdekken van de sleutel bij een bekend paar plaintext-ciphertext. Als deze sleutel bekend is, kan alle andere ciphertext van diezelfde sleutel gedecodeerd worden. DES is een encryptiemethode die 64 bit berichten met een 56 bit sleutel codeert in 64 bit door het gebruik van substitutie en transpositie meerdere keren uit te voeren. Door cryptanalyse zijn er technieken bekend waardoor DES sneller gekraakt kan worden dan met de brute force methode. Ook zijn er andere methoden voorgesteld zoals speciaal geconstrueerde silicium von Neumann-computers, die DES zouden kunnen breken in niet meer dan 7 uur [25]. De manier waarop DNA computing gebruikt kan worden om achter de sleutel te komen, gegeven één plaintext-ciphertext paar, wordt beschreven door Boneh et. al [3]. Om plaintext te coderen wordt gebruik gemaakt van een zogenaamd DES-circuit, opgebouwd uit P-boxes en S-boxes. P-boxes is een stuk hard- of software die een bitreeks transponeert aan de hand van een sleutel. Een S-box substitueert een bitreeks. Bij coderen van een plaintext bericht wordt dit DES-circuit 16 keer achter elkaar doorlopen [22]. Voor decryptie van een ciphertext zijn slechts kleine aanpassingen van het DES-circuit nodig. Boneh beschouwt daarom in zijn artikel de encryptie- en decryptie-circuits als gelijkwaardig. Het plan van Boneh om de sleutel k te achterhalen bij een bekend plaintext-ciphertext (M,E) paar is al volgt: 1. Construeer het decryptie circuit DES-1 in DNA. 2. Genereer voor elke mogelijke sleutel een paar bitreeks (kn ,Mn)= DES-1 (E,kn). 3. Extraheer alle DNA strengen die M bevatten. 4. Extraheer k uit deze DNA strengen. Boneh beschrijft in zijn artikel de constructie van het DES-circuit met gebruik van DNA operaties. Dit wordt gedaan door bitreeksen te gebruiken, gecodeerd als reeksen van basenparen. Verder gebruikt hij de booleaanse operatie XOR en lookup tables. Voor meer informatie over deze operaties zie [3].

5.3.

Voordelen

DNA computing biedt twee voordelen met betrekking tot het gebied van cryptografie. Ten eerste de hoge opslagdichtheid van DNA. Zoals beschreven in het hoofdstuk over informatieopslag kan er veel meer data worden opgeslagen dan met conventionele opslagmedia, zoals magnetische schijven. Op het gebied van steganografie is dit van cruciaal belang, omdat de grootte van de dummy data ten opzichte van het geheime bericht de sterkte van deze methode aangeeft. Ook bij one-time pads is dit een belangrijk voordeel, omdat veel grotere hoeveelheden data dan tot nu toe mogelijk ermee gecodeerd kunnen worden. Een andere karakteristiek van DNA computing is de mogelijkheid tot parallelle verwerking. Deze eigenschap wordt gebruikt door Boneh bij zijn algoritme voor het kraken van DES. Het genereren van alle mogelijke sleutel-plaintext paren gebeurt parallel. Dit zorgt ervoor dat het probleem in lineaire tijdcomplexiteit opgelost kan worden, dat wil zeggen dat de methode in DNA beter schaalbaar is dan geïmplementeerd op conventionele computers.

5.4.

Nadelen

Het probleem bij DNA computers is dat de operaties weliswaar parallel uitgevoerd worden, maar dat de rekentijd groot is, vergeleken bij conventionele computers. Boneh geeft als schatting dat het breken van DES in ongeveer drie maanden mogelijk moet zijn met zijn methode. Dit steekt natuurlijk schril af tegen de zeven uur van Wiener met zijn methode van speciale (silicium) hardware [25].

6. Signaalverwerking Een tweede toepassing van DNA computing is signaalverwerking. Deze sectie beschrijft een toepassing van de verwerkingscapaciteit van DNA in digitale signaalverwerkingsproblemen (DSP problemen). Ondanks dat digitale signalen worden gebruikt als invoer in gegevensverwerkingtoepassingen van DNA (bijvoorbeeld in databases [13, 20]), zijn er geen eerdere onderzoeken geweest naar het toepassen van DNA computing voor het oplossen van DSP problemen. Eerst zullen we kijken naar een toepassing van een signaalverwerkingsprobleem dat als bewijs kan dienen voor op DNA gebaseerde DSP problemen. Vervolgens wordt het belangrijkste aspect van deze toepassing besproken en ook de toepassing van de uitvoering van DNA gegevensbestanden op digitale signalen.

6.1.

DNA verwerking toegepast op gelijkheidsproblemen

Toepassingen in signaal- en beeldverwerking vereisen de gelijkenis van ofwel twee signalen ofwel delen van de twee signalen. Er bestaan verschillende soortgelijke problemen, waar het ongelijkheidsschattingsprobleem [7] een voorbeeld van is. Men heeft veel werk verricht aan het ongelijkheidsschattingsprobleem. Criteria die hiervoor het meest gebruikt worden, zijn fotometrische gelijkenis en ruimteconsistentie. Er is een beperking die ruimteconsistentie oplegt aan het ongelijkheidsgebied, te weten ordering constraint. Dit houdt in dat als men een pixel A heeft die links van een pixel B staat, dat deze orde gehandhaafd moet blijven door zowel pixel A als pixel B. In de meeste DSP toepassingen worden de beschikbare gegevens verstoord door ruis dat als een bijkomend en stationair proces wordt gemodelleerd. Gelijkheidsproblemen kunnen opgelost worden met behulp van DNA [23]. Indien het ongelijkheidsschattingsprobleem goed genoeg geformuleerd is, kan dit probleem opgelost worden door gebruik te maken van DNA moleculen. Het ontharden van DNA kan heel gemakkelijk gebeuren met behulp van een computer en is dus toepasbaar om dit probleem op te lossen [26]. Als men een DSP probleem wil oplossen met behulp van DNA computing, dan is de eerste stap het coderen van de te vergelijken signalen in een reeks van de basen. Als men een codewoord ontwerpt, zijn er bepaalde beperkingen om niet-specifieke kruising (non-specific hybridization) te voorkomen omdat bij de bestaande toepassingen op bio-computing deze niet wenselijk is. Echter kan de niet-specifieke kruising wel nuttig (en zelfs noodzakelijk) zijn in de toepassingen van de signaalverwerking. Dit omdat een nauwkeurige gelijkenis vaak genoeg niet mogelijk is vanwege de aard van de signalen en de aanwezigheid van ruis. Verder is er ook nog een gelijkenis gewenst in de mean-squared-error (MSE). Het effect van temperatuurschommelingen op DNA moleculen is afhankelijk van hoe hun basen zijn gecombineerd in de streng [16]. Als men deze verhoudingen heel goed plaatst en aan codewoorden van DNA een signaalwaarde geeft, kan men de gelijkenissen controleren door de temperatuur van de kruisingen aan te passen. Om een oplossing te vinden voor het ongelijkheidsschattingsprobleem, kan men gebruik maken van het ontharden van DNA. Dit gebeurt dan doordat de linkerbeeldlijn wordt gecodeerd in een bepaalde DNA reeks en de rechterbeeldlijn wordt gecodeerd in het WatsonCrick complement van deze reeks. Als beide DNA reeksen in een oplossing worden gedaan, zal dit ertoe leiden dat reeksen die gelijk zijn aan elkaar een helix vormen. Als gevolg van de nietspecifieke kruising zullen de reeksen die niet gelijk zijn aan elkaar ‘bellen’ vormen [23]. Indien men de codewoorden zorgvuldig ontwerpt, kan het ontharden van DNA een krachtig hulpmiddel zijn om een optimale oplossing te vinden. Als men de lengte van elke bel opmeet en ook de positie van elke bel bepaalt vanuit beide richtingen, dan verkrijgt men de gezochte ongelijkheidsschattingen.

6.2.

Op DNA gebaseerde gelijkenis van digitale signalen.

Het vertonen van gelijkenissen tussen digitale signalen is een fundamenteel probleem dat voorkomt bij vele signaalverwerkingstoepassingen. Het ontharden van DNA wordt hier gebruikt als zoek- of classificatiemechanisme door de gelijkenissen tussen signalen te kwantificeren. Kenmerkend voor het gelijkheidsprobleem zijn de onnauwkeurigheid van gelijkenissen en de aanwezigheid van ruis. Ruis is vaak onvermijdelijk en komt vooral uit het signaalvormingsproces, het transmissiemedium, het opnameprocédé of een combinatie van deze drie. Kortom om het gelijkheidsprobleem op te lossen, is het noodzakelijk om de gelijkenissen tussen signalen te kwantificeren. Digitale signalen moeten eerst in reeksen van het DNA alfabet (A,C,G,T) gecodeerd worden om een DNA oplossing te kunnen genereren. Om ruis en onvolmaakte gelijkenissen op te vangen, wordt de Noise Tolerance Constraint (NTC) geïntroduceerd. NTC zorgt ervoor dat de onvolmaakt gelijkenissen gecontroleerd kunnen worden door de temperatuur van de kruisingen aan te passen, indien men de onderlinge verhoudingen van DNA basen zorgvuldig plaats en signaalwaarden toekent aan codewoorden [23, 24]. NTC geeft geen oplossing voor het codewoordontwerp, maar geeft slechts een verband tussen gehele waarden en het smeltpunt van DNA opeenvolgingen.

6.3.

Op DNA gebaseerde opslag van digitale signalen

Er wordt op dit moment onderzoek gedaan naar het gebruik van DNA als opslagmiddel voor digitale signalen. Men gaat er vanuit dat een op DNA gebaseerde opslag ons zo bekende magnetische schijf niet gaat vervangen, maar dat het wel een compacte, economische en duurzame vorm van opslag kan verstrekken. Als men andere opslagmiddelen vergelijkt, dan biedt het gebruik van DNA om digitale signalen of gegevens op te slaan veel voordelen. Gegevensbestanden repliceren en het opvragen van gegevensbestanden kan op allerlei manieren plaatsvinden. Als men vraagmoleculen krijgt, kan met behulp van ontharden van DNA op een zeer efficiënte manier worden gezocht naar gelijkwaardige moleculen in het gegevensbestand. Hierbij is de vraagtijd niet afhankelijk van de grootte van het gegevensbestand, omdat het hele bestand parallel doorzocht kan worden, dit in tegenstelling tot digitale gegevensbestanden.

6.4.

Voordelen

De voordelen van het gebruik van DNA om gegevens digitaal op te slaan, voornamelijk signalen, omvatten: informatiecompactheid, economische replicatie van gegevensbestanden, efficiënte vraagmechanismen, het opvangen van ruis met behulp van NTC en een vraagtijd die onafhankelijk is van de grootte van het gegevensbestand.

6.5.

Nadelen

Het oplossen van DSP problemen met behulp van DNA is nog niet realiseerbaar met de huidige technieken.

7. Conclusie Er wordt vooruitstrevend onderzoek gevoerd naar de mogelijkheden van DNA computing, waarbij in mindere mate de praktische toepasbaarheid in ogenschouw wordt genomen. Dit artikel tracht desondanks verschillende praktische toepassingsgebieden van DNA computing te onderzoeken. Om praktische informaticatoepassingen te implementeren zijn er verschillende hulpmiddelen nodig. Het is noodzakelijk om informatie op te slaan, zowel de te verwerken informatie als programmacode. Uit het onderzoek is gebleken dat informatieopslag goed

mogelijk is met DNA computing, het biedt zelfs voordelen zoals een grote opslagcapaciteit en constante toegangstijden. De opslagcapaciteit is zo groot dat het volledige gebruik ervan uitzonderlijk is. Vooralsnog zijn de toegangstijden lang maar deze zullen met de chemische vooruitgang afnemen. Parallellisatie met behulp van DNA computing kan voor verschillende doorbraken in de technologische sector zorgen. Zo zullen problemen, waarvan de oplossingen veel tijd vergen, in een acceptabel tijdsinterval opgelost kunnen worden. Bovendien kan het voor een schoner milieu zorgen, vanwege het feit dat biologische machines een stuk zuiniger zijn dan welke huidige machine dan ook. Cryptografie en signaalverwerking zijn beiden specifieke toepassingen die zowel informatieopslag als parallelle verwerking gebruiken. De getrokken conclusies gelden dus ook voor deze specifieke toepassingen. Concluderend kan gesteld worden dat DNA computing zeer veel potentie heeft om een algemeen toepasbare verwerkingsmethode te worden. Er is echter nog veel onderzoek nodig naar snellere methodes voor DNA manipulatie voordat deze praktisch toepasbaar worden. De toekomst van DNA computing is voorlopig nog afhankelijk van de vorderingen in de biochemie.

Referenties [1] Adleman, L. M. (1994). Molecular Computation of Solutions to Combinatorial Problems. Science, 266:1021-1024. [2] Baum, E. (1995). Building an Associative Memory Vastly Larger Than the Brain. Science, 268:583-585. [3] Boneh, D., Dunworth, C., & Lipton, R. (1996), Breaking DES using a molecular computer. Proceedings of DNA-Based Computers, volume 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society. [4] Clelland, C. T., Risca, V., & Bancroft, C. (1999). Hiding messages in DNA microdots. Nature, 399:533-534. [5] Gehani, A., LaBean, T.H., & Reif, J.H. (1999). DNA-based Cryptography. Proceedings of 5th International Meeting on DNA Based Computers, MIT, 14-15 June. [6] Guarnieri, F., Fliss, M., & Bancroft, C. (1996). Making DNA add. Science, 273:220-223. [7] Haralick, R.M. and Shapiro, L.G. (1993). Image matching in Computer and Robot Vision. Reading MA: Addison-Wesley, vol. II, Ch. 16. [8] Hug, H. & Schuler. R. (2001). DNA-based parallel computation of simple arithmetic. Proceedings of DNA Computing, 7th International Meeting on DNA Based-Computers, DNA 2001, Tampa, U.S.A., 10-13 June 2001, 159–166, University of South Florida. [9] Kari L. (1997). DNA Computing: Arrival of Biological Mathematics. Math. Intelligencer, 19(2):9-22. [10] Katsányi, I. (2003). On Implementing Relational Databases on DNA Strands. Acta Cybernetica, 16(2):259-270. [11] Li, K. (1996). Massively Parallel Biological Computing. NP-Complete, 4(1):5-8. [12] Lipton, R. J. (1995). Using DNA to solve NP-Complete Problems. Science 268:542-545. [13] Mills, A.P., Yurke, B. & Platzman, P.M. (1999). Article for analog vector algebra computation. Biosystems, 52(1-3):175–180. [14] Ogihara, M., & Ray, A. (1999). Executing parallel logical operations with DNA. Congress on Evolutionary Computation, Washington, DC, pages 972-979, IEEE. [15] Peterson, I. (1996 July 2). Ivars Peterson's MathLand: DNA adds up. [WWW document] http://www.maa.org/mathland/mathland_7_22.html. [16] Peyret, N., Seneviratne, P.A., Allawi, H.T. & SantaLucia, Jr., J. (1999). Nearest-neighbor thermodynamics and NMR of DNA sequences with internal A-A, C-C, G-G, and T-T mismatches. Biochemistry, 38(12):3468–3477. [17] Pisanti, N. (1997). A survey on DNA-Computing. (Report No. TR-97-07). Pisa, Italy: Universita di Pisa Departimento di Informatica. [18] Qiu, Z. F., & Lu, M. (2000). A new solution for Boolean Circuit with DNA Computer. Technical report, Texas A&M University, Department of Electrical Engineering.

[19] Reif, J. H. (1998) Paradigms for Biomolecular Computation. Proceedings of First International Conference on Unconventional Models of Computation, Auckland, New Zealand, January 1998, 72-93. [20] Reif, J., LaBean, T., Pirrung, M., Rana, V., Guo, B., Kingsford, C. & Wickham, G. (2001). Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability. Proceedings of DNA Computing, 7th international Meeting on DNA-Based Computers, DNA 2001, Tampa, U.S.A., 10-13 June 2001, 231-247, University of South Florida. [21] Rooβ, D. & Wagner, K. W. (1996). On the power of DNA Computing. Information and computation 131(2):95-109. [22] Tanenbaum, Andrew S. (2003). Computer networks (4th ed.). Upper Saddle River, New Jersey: Prentice Hall PTR. [23] Tsaftaris, S.A. (2003). DNA-based digital signal processing. M.S. thesis, Evanston: Northwestern University, Deptartment of Electrical Computer Engineering. [24] Tsaftaris, S.A., Katsaggelos, A.K., Pappas, T.N., Papoutsakis, E.T. (2001). DNA-based matching of digital signals. Proceedings of International Conference on Acoustics, Speech, and Signal Processing, vol. 5, Montreal, Quebec, Canada, May 17–21, 2004, 581–584, IEEE. [25] Wiener, M. J. (1996). Efficient DES Key Search. presented at the Rump session of Crypto ‘93. Reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, 31-79. [26] Winfree, E. (1995). On the computational power of DNA annealing and ligation. Proceedings of DNA-Based Computers: DIMACS Workshop, 4 April, 1995, 199–221. [27] Wong, P. C., Wong, K.-K. & Foote, H. (2003). Organic Data Memory using the DNA Approach. Communications of the ACM, 46(1):95-98.