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 worden een aantal toepassingsgebieden van DNA computing onderzocht. Er wordt met name gekeken naar de praktische toepasbaarheid op deze toepassingsgebieden. Als inleiding is er een korte introductie gegeven tot DNA computing. Vervolgens worden drie algemene toepassingsgebieden beschreven, te weten parallelle verwerking, informatieopslag en rekenkundige operaties. 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 zijn met betrekking tot de snelheid van DNA operaties.

1. Inleiding In de computerkunde zijn veel problemen bekend, die niet in polynomiale tijd opgelost kunnen worden. In de zoektocht naar een manier om een oplossing in een doenlijk tijdsbestek te construeren is men beland op een biologisch spoor. De moleculaire biologie wordt nu gebruikt om oplossingen voor problemen uit de computerkunde 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. Sindsdien is er veel onderzoek gedaan naar de mogelijkheden van DNA met betrekking tot calculaties. Hierbij is in mindere mate de praktische toepasbaarheid beschouwd, die het doel is van dit artikel. DNA computing wordt niet alleen toegepast als oplossingsmethode voor ondoenlijke problemen, maar kan ook voor diverse toepassingsgebieden worden gebruikt, waarvan er in dit artikel enkelen aan bod zullen komen. Na een algemene inleiding over DNA zal worden beschreven hoe er met dit erfelijke materiaal geprogrammeerd kan worden en hoe er mathematische operaties uit te voeren zijn. Hierbij is het van grote noodzaak dat er informatie opgeslagen wordt en DNA leent zich hier uitstekend voor, zoals dat beschreven zal worden in het hoofdstuk over informatieopslag. Deze informatie dient bewerkt te worden en het liefst op een zo efficiënt mogelijke manier. In het hoofdstuk over parallelle processing zal hierop dieper worden ingegaan. Dit zijn drie brede toepassingsgebieden die als hulpmiddel gebruikt kunnen worden om praktische toepassingen te implementeren met behulp van DNA. Vervolgens worden er ook twee specifieke toepassingen beschreven om het onderzoek een wat concretere vorm aan te meten. Eén van deze specifieke toepassingen is cryptografie. Bij de behandeling van cryptografie komen zowel encryptie als het kraken van encryptiemethoden aan de orde. Tenslotte 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, die in dit artikel aan bod zullen komen.

2. DNA Computing 2.1.

Wat is DNA?

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. DNA (desoxyribonucleïnezuur) bevat de complete erfelijke informatie van een bepaald 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. Deze twee groepen worden ook wel aangeduid als respectievelijk 5’ en 3’ en zijn ook nog elkaars complement. Wanneer nucleotiden samengebracht worden om een keten te vormen wordt het ene uiteinde van de ene nucleotide gebonden aan het complementaire uiteinde van een andere nucleotide. Daarom kunnen we de opeenvolging van basen in zulke ketens beschouwen alsof zij geordend zijn. Deze ordening speelt een belangrijke rol, omdat zij restricties legt op het uitvoeren van operaties op de strengen [1]. 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. • • • • • • • •

Synthese: het creëren van een gewenste DNA keten. Dit is mogelijk voor ketens tot een bepaalde lengte. Extractie: het extraheren van een bepaalde volgorde van nucleotiden uit een DNA keten. Amplificatie: alle ketens in de reageerbuis dupliceren. Polymerase kettingreactie (PCR): een machine die enkele operaties op DNA mogelijk maakt. Lengte: ketens met een verschillende lengte scheiden door middel van een bepaalde gel. Ontharden: een paar vormen van twee enkele complementaire DNA ketens. Smelten: een paar van twee complementaire DNA ketens scheiden. Detecteer: controleren of de te controleren reageerbuis tenminste één DNA keten bevat [2].

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, waarvan de praktische toepasbaarheid het onderwerp van dit artikel is. 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 werd was zeer groot, maar het aantal processoren dat parallel kon draaien was klein. Het hoofddoel van de eerdergenoemde nieuwe ideeën was niet het aantal stappen per tijdseenheid te vergroten, maar het aantal processoren 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 processoren te gebruiken, zo kwam DNA computing tot stand [2, 3]. Adleman was de eerste, die de berekeningskracht van DNA ter sprake bracht. Dit deed hij door enkele instanties van het gerichte Hamiltoons pad probleem op te lossen door middel van biologische experimenten met DNA strengen [2, 4], waarover meer informatie kan worden gevonden in het hoofdstuk over programmeren met DNA. 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 gebruikte het werk van Adleman om elk NP probleem polynomiaal op te lossen 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 [3]. In 1995 werd DNA computing nog populairder: het SAT probleem werd opgelost met een nieuw en praktischer algoritme [5]. Ook werd eraan gedacht DNA nu te gebruiken als geheugen, waarover meer te vinden is in het hoofdstuk over informatieopslag. 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. Daarna werd er een moleculaire programmeertaal gepresenteerd: DNAPascal, die in de volgende sectie nader toegelicht zal worden. Deze taal gebruikte enkele datatypen en instructies uit de reguliere programmeertaal, maar er werden nieuwe operaties en testen toegevoegd, die correspondeerden met biologische operaties op DNA ketens [2]. Hierover meer in het volgende hoofdstuk. 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. Programmeren met DNA Er zijn verschillende modellen (combinaties van biologische operaties) voorgesteld om DNA computing mee te realiseren. Denk hierbij aan het model van Adleman, het Sticker model, het PAM model en splicing systems [2].

De bestaande modellen maken gebruik van primitieve biologische operaties zoals beschreven in het vorige hoofdstuk. Deze bio-operaties zullen worden gebruikt om programma’s mee te schrijven. Het idee is dat een tube met DNA als invoer dient en na manipulatie één of meer reageerbuizen als uitvoer geeft. Het eindresultaat kan ook simpelweg ‘ja’ of ‘nee’ zijn afhankelijk van de aan- of afwezigheid van een bepaalde DNA molecule in uitvoerreageerbuis. Dit hoofdstuk belicht de wijze waarop DNA computing kan worden gebruikt om programma’s mee te realiseren. Allereerst komt het experiment van Adleman aan bod. Hier wordt aangegeven hoe een specifiek probleem kan worden gecodeerd in DNA. Vervolgens datarepresentatie met behulp van DNA en daarna een voorbeeldcodering van een optelling. Ten slotte wordt de algemene toepasbare programmeertaal DNA Pascal besproken.

3.1.

Het experiment van Adleman

Adleman richte zich op een specifiek combinatorisch probleem, namelijk het Hamiltoons pad probleem. Hij realiseerde van een niet-deterministische oplossing een biologische implementatie. DNA computing volgens Adleman bestaat uit twee fasen: 1 Het genereren van alle mogelijke oplossingen met DNA moleculen. 2 Het antwoord selecteren uit de DNA moleculen. Het Hamiltoons pad algoritme werd als volgt gecodeerd: elke knoop werd gecodeerd in een DNA streng bestaand uit 20 basen, waarover meer te vinden is in de vorige sectie. Elk gericht pad werd gecodeerd met een streng bestaande uit de tweede helft van de eerste knoop en de eerste helft van de tweede knoop. Met de operaties lengte, smelten en detecteer wordt nagegaan of er een oplossing bestaat. Voor een uitgebreide uitleg over de implementatie van het Hamiltoons pad algoritme [2, 4]. Er zijn intussen meerdere biologische algoritmen bedacht om NP problemen op te lossen. Zo zijn er oplossingen bedacht voor onder andere het 3-kleurenprobleem en het realiseren van een niet-deterministische Turing machine met één tape. Deze oplossingen zijn echter gericht op een specifiek probleem en een specifiek algoritme. Er is een algemener model nodig, waarmee verschillende problemen kunnen worden gecodeerd.

3.2.

Datarepresentatie met DNA

In modellen die niet zijn gericht op een specifiek probleem, moet het mogelijk zijn om een bitreeks te coderen en daarna te manipuleren. Dit wordt verwezenlijkt door elk bit te associëren met een bepaalde DNA streng. De aanwezigheid van een bepaalde DNA streng in de DNA emulsie betekent dat het met die keten geassocieerde bit op 1 is gesteld. Per bit zijn er dus altijd twee DNA strengen (de streng en het complement) in een oplossing. Om data efficiënter op te slaan maakt het Sticker model [2] 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. In plaats van één bit per dubbele streng, verkrijgen we k bits per dubbele streng.

Het manipuleren van complexen is hierdoor efficiënter. Het kraken van DES bijvoorbeeld, gaat veel efficiënter wanneer gebruik wordt gemaakt van het Sticker model, dan wanneer er van één streng per bit wordt uitgegaan. DES wordt besproken in het hoofdstuk DNA cryptografie.

3.3.

Optellen met DNA

Het is duidelijk dat operaties die kunnen worden uitgevoerd op DNA, afhangen van de wijze waarop data in het DNA is gecodeerd. Er wordt in deze paragraaf een concreet voorbeeld van een biologisch programma beschreven, dat de wiskundige operatie optelling simuleert. 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 [9] zijn erin geslaagd om een op DNA gebaseerd optelalgoritme te implementeren. In hun algoritme zijn natuurlijke getallen zodanig gecodeerd dat die door middel van primer extention reacties kunnen worden opgeteld. Dit zijn reacties waarbij DNA strengen tot een volledige helix worden gevormd. 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 [9]. 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 in ongeveer twee dagen te doen is, relatief weinig werk in DNA computing, maar wel extreem veel vergeleken met traditionele computing.

3.4.

DNA Pascal

Aan de hand van het voorgaande is het niet moeilijk om te bedenken dat er in de toekomst biocomponenten zoals adders en dividers zullen bestaan die kunnen worden gebruikt om biocircuits te bouwen. Deze zullen wat structuur betreft waarschijnlijk geheel verschillen van hun elektronische varianten. Om de toepasbaarheid van deze bio-circuits te vergroten is het nodig om deze op een hoger niveau te kunnen programmeren. Om deze reden belichten wij nu de programmeertaal DNA Pascal. Het is gebruikelijk om aritmetische en booleaanse operaties uit te voeren op numerieke en booleaanse data. DNA Pascal maakt echter gebruik van nieuwe operaties en data typen. De datatypen zijn positieve integers, arrays en sets. Uitgangspunt is dat er woorden kunnen worden gevormd uit het alfabet DNA = {A, C, T, G} . Deze noemen we woordvariabelen. Met deze woorden kunnen

∑

integers en sets worden gevormd. Van integers kunnen tevens arrays worden gebouwd. Deze noemen we natuurlijke variabelen.

Enkele operaties zijn IN initialization T:=IN(m), UN union T:=T1 ∪ T2, AS assignment T:=T1 en EX extraction T1:=EX(T1,m,a). Ook zijn er naast de gebruikelijke testen tussen numerieke en booleaanse data (<, >, = =) enkele nieuwe testen voor de set datatype. De nieuwe condities waarop kan worden getest zijn SU Subset T1 ⊆ T2 , EM Detect T = φ , ME Membership x ∈ T . Hierbij stellen T, T1 en T2 sets voor en stelt x een variabele voor. Het valt op te merken dat deze operaties en tests in 1 stap kunnen worden uitgevoerd. Ter illustratie een DNA Pascal implementatie van het 3-SAT probleem [2]:

begin T0 :=IN(n); for i :=0 to k do begin T1 :=EX(T0, α [i],a[i]); T2 :=EX(T0, β [i],b[i]); T3 :=EX(T0, γ [i],c[i]); T0 :=T1 ∪ T2; T0 :=T0 ∪ T3 end; if T= ∅ then reject else accept end

3.5.

Praktische toepasbaarheid

Biologische circuits zijn te vergelijken met elektronische circuits. Met elektronische circuits is het mogelijk om in hardware een compleet computerprogramma te construeren. Dus door de juiste draden met de juiste componenten te verbinden en het geheel op een energiebron aan te sluiten bouw je in principe al een programma. Hier bovenop kan nog software worden geplaatst waardoor veel complexere programma’s kunnen worden gemaakt. Hetzelfde geldt voor biologische circuits. Het zal mogelijk zijn om biologische componenten te maken die bijvoorbeeld door enzymen met elkaar zullen worden ‘verbonden’. Er zullen bio-systemen voor een specifiek doel worden gemaakt, maar ook voor algemene doeleinden waar software op kan draaien. Programma’s voor deze systemen zullen geschreven worden in DNA Pascal of een soortgelijke taal.

4. Informatieopslag 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. 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.

4.1.

DNA en dataopslag

Dat DNA in de praktijk als geheugen kan worden gebruikt, bewijst het experiment dat in [10] wordt beschreven. Hierbij werd een eenvoudig coderingsschema gebruikt om een boodschap om te zetten naar DNA nucleotiden. Dit DNA werd vervolgens aangemaakt en op een vel papier gedaan. Het vel papier met DNA werd per post verstuurd. Nadat het vel papier met de post terugkwam wist men de boodschap uit het DNA te achterhalen. In hoofdstuk 6 wordt dit experiment nader toegelicht.

4.1.1.

Associatief geheugen

Baum beschrijft in zijn artikel de mogelijkheid om DNA te gebruiken als associatief geheugen [11]. 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 tweede 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, beschreven in het deel over operaties op DNA, 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, zie de sectie over operaties, 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, DNA moleculen met een bepaalde subreeks worden gescheiden van de overige DNA moleculen. 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.

4.1.2.

Relationele Databases

Experimenten hebben aangetoond dat het in de praktijk zelfs mogelijk is om grootschalige databases in DNA [12] te implementeren. Daarbij was het mogelijk om associatief door de database te zoeken. Katsányi neemt dit nog een stap verder [13]. 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.

4.1.3.

Databescherming

DNA reeksen zijn erg gevoelig voor invloeden van buiten af: een los DNA molecule kan eenvoudig worden vernietigd door ongunstige omstandigheden [14], zoals extreme temperaturen en straling. Als DNA onder de juiste omstandigheden wordt bewaard, is deze gevoeligheid geen probleem. Voor sommige toepassingen echter van geheugen 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 [14]. 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 genetisch 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. Deze bacterie is bestand tegen extreme omstandigheden zoals extreme temperaturen, ultraviolette en ioniserende straling. Een tiende procent van de dosis van ioniserende straling is al dodelijk voor de mensen.

4.2. 4.2.1.

Voor- en nadelen van dataopslag met DNA 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, een conventioneel geheugen kan ‘slechts’ 109 bits per gram opslaan [12] en een liter water met DNA kan 108 terabytes aan informatie opslaan [13]. Baum vindt vaten met DNA die evenveel informatie als de menselijke hersenen kunnen opslaan niet ondenkbaar [11]. Een ander groot voordeel is dat het zoeken door DNA databases met constante tijd kan worden uitgevoerd [13]. 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 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.

4.2.2.

Nadelen

DNA geheugen is gebaseerd op chemische reacties. Dit brengt een 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. De informatie kan voor bescherming bij organismen worden geïnjecteerd. Dit organisme zal zich vermenigvuldigen en de informatie doorgeven, maar bij de vermenigvuldiging is mutatie niet uitgesloten. 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 [11].

4.3.

Praktische toepasbaarheid

Geheugen op basis van DNA heeft een zeer vruchtbare toekomst. Onderzoeken en experimenten hebben aangetoond dat DNA geheugen niet alleen in theorie, maar ook in de praktijk werkt. De mogelijkheden reiken ver boven die van conventionele geheugens. De enorme capaciteit en constante zoektijden zijn twee grote voordelen. Het grootste nadeel is de lange toegangstijd, maar dankzij chemische vooruitgang wordt het mogelijk deze operaties steeds sneller uit te voeren.

5. Parallelle operaties met behulp van DNA computing DNA computing onderzoekt 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 een nieuw soort computer [15]. 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 [16]. 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.

5.1. 5.1.1.

Massief Parallelle Biologische Machines 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.

5.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 [17]. 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.

5.1.3.

Parallelle rekenkunde

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 door het implementeren van booleaanse operaties die gebruik maken van bits. Dit algoritme had echter beperkingen. Zo konden er alleen twee getallen opgeteld worden, waarbij het massieve parallelle aspect tekort geschoten werd. Nog een nadeel was dat de uitvoer anders was dan de invoer, namelijk gecodeerd. Dit is cruciaal aangezien nu geen herhaaldelijke operaties uitgevoerd konden worden. Vervolgens kwamen er nog verscheidene algoritmen voor het oplossen van dit rekenkundige probleem. Totdat Rubin et al. een demonstratie gaven van een experimentele demonstratie van sequentiële rekenoperaties. Dit had als gevolg dat ook omkeerbare rekenoperaties konden worden uitgevoerd [18]. Zie voor verdere uitleg het hoofdstuk over programmeren met DNA.

5.1.4.

Versnelling van operaties

Beaver, Reif, en Papadimitrion hebben elk individueel 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 en tijd O(s), gesimuleerd kunnen worden in polynomiale tijd.

5.2.

Voordelen

Biologische machines hebben ten opzichte van de huidige (super)computers 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.

5.3.

Nadelen

Het probleem van parallelle computing 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 [2, 4].

5.4.

Praktische toepasbaarheid

Parallellisatie met behulp van DNA computing kan voor verschillende doorbraken in de technologische sector zorgen. Zo zullen de nu nog onoplosbare problemen in een geaccepteerd tijdsinterval opgelost kunnen worden. Ook kan het voor een schoner milieu zorgen, vanwege het feit dat biologische machines een stuk zuiniger zijn dan welke huidige machine dan ook.

Beperking in geheugen dat in de praktijk een grote rol speelt, zal niet opgaan voor biologische machines. Dergelijke machines beschikken over zo een groot geheugen dat het volledige gebruik ervan zeer uitzonderlijk is. Voordat dit alles echter gerealiseerd kan worden moet er nog veel geïnvesteerd worden in onderzoeken naar het ontwikkelen en implementeren van betere algoritmen voor betere benutting van DNA computing.

6. Cryptografie De veiligheid 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 geëncrypteerd moet worden, is snelheid van de encryptiemethoden van belang. DNA computing brengt nieuwe mogelijkheden voor de cryptografie met zich mee. Zoals beschreven in voorgaande hoofdstukken zijn parallelle verwerking en geheugen krachtige toepassingen 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. Dit hoofdstuk zal twee methoden beschrijven voor encryptie door middel van DNA computing evenals een methode beschrijven 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.

6.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, omdat er geen onderzoek bekend is op dit gebied met betrekking tot DNA computing. 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 [19].

6.2. 6.2.1.

Cryptografie door middel van DNA computing 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 [10]. Zij hebben uit de doeken gedaan hoe steganografie mogelijk is door berichten geëncodeerd 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. Deze reeksen kunnen gebruikt worden om polymerase kettingreacties op te wekken. De ontvanger kent deze sequences en kan de juiste enzymen gebruiken om het bericht te amplificeren, voor meer uitleg over amplificatie en polymerase kettingreacties zie operaties op DNA, 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 [10].

6.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 gebruikt. De bitreeks is van dezelfde grootte als de te encoderen data. Om de encryptie tot stand te brengen wordt de plaintext eveneens 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 [19]. 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 [19]. DNA heeft een aantal karakteristieken, dat 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 encrypteren door middel van one-time pads. Er zijn hierbij drie stappen nodig: het encoderen van de sleutel en plaintext in DNA, het genereren van de sleutel en het implementeren van de booleaanse XOR-operatie in DNA operaties [20].

Voor de encodering 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 [20].

6.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 bits berichten met een 56 bits sleutel codeert in 64 bits door het gebruik van substitutie én transpositie meerdere keren geconcateneerd. Door cryptanalyse zijn er technieken bekend waar door 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 [21]. 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 [1]. Om plaintext te coderen wordt gebruikt 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 [19]. 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. Op de details wordt hier niet verder ingegaan [1].

6.3.

Praktische toepasbaarheid

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. 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 [21]. Concluderend kan gezegd worden dat DNA computing wel degelijk praktisch voor cryptografie gebruikt kan worden. Dit geldt voor de gevallen waarbij hoge informatiedichtheid belangrijker is dan encryptie- of decryptiesnelheid.

7. Signaalverwerking Tegenwoordig ziet men vaak dat er veel interactie plaatsvindt tussen biologie en signaalverwerking. Met behulp van de technieken van digitale signaalverwerking (DSP) zijn er veel oplossingen gevonden voor bio-informaticaproblemen. Door het gebruik van de normale chemie zijn er oplossingen gevonden voor computerproblemen en dit heeft geleid tot het ontstaan van verwerken van problemen met behulp van DNA, ook wel gekenmerkt als biocomputing. Dit deel van de paper beschrijft een toepassing van de gegevensverwerking van DNA in DSP problemen. Ondanks dat digitale signalen worden gebruikt als invoer in gegevensverwerkingtoepassingen van DNA (bijvoorbeeld in databases [12, 23]), zijn er geen eerdere onderzoeken geweest bij het toepassen van gegevensverwerking van DNA principes in het oplossen van DSP problemen. Eerst zal gekeken worden naar het probleem van de signaalverwerking 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 implementatie van DNA gegevensbestanden op digitale signalen.

7.1.

DNA verwerking toegepast op gelijkheidsproblemen

Toepassingen in signaal- en beeldverwerking vereisen de gelijkenis van één van beide signalen of op zijn minst segmenten van de twee signalen, zoals uitgedrukt door de verschuivingen vereist voor één signaal om aan te passen aan de ander. Er bestaan verschillende soortgelijke problemen, het ongelijkheidsschattingsprobleem is een voorbeeld dat het idee beschrijft. Men heeft veel werk verricht aan het ongelijkheidsschattingsprobleem [22]. Criteria die hiervoor het meest gebruikt worden, zijn fotometrische gelijkenis en ruimteconsistentie welke de onderzoeksruimte voor de verplaatsing of ongelijkheidsvector beperkt. Er is nog een extra beperking die ruimteconsistentie oplegt aan het ongelijkheidgebied te weten ordering constraint. Dit houdt in dat als men een pixel A heeft die links van een pixel B staat in het linkerbeeld, 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 bijkomende en stationair proces wordt gemodelleerd. Gelijkheidsproblemen kunnen opgelost worden met behulp van de DNA samenstelling en een emulsie van DNA [25]. 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 makkelijk gebeuren met behulp van een computer en dus toepasbaar om dit probleem op te lossen [27]. Als men een probleem wil oplossen met behulp van DNA verwerking, dan is het eerste wat men moet doen de digitale gegevens coderen in een opeenvolging van de basen van DNA. De te vergelijken signalen moeten dan in DNA worden gecodeerd. Als men een codewoord ontwerpt, zijn er beperkingen die worden gesteld als men gebruik maakt van DNA. Deze zijn belangrijk voor de bestaande toepassingen op bio-computing, waarvoor de niet-specifieke kruising (non-specific hybridization) 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). De thermodynamische stabiliteit van duplexen kunnen beïnvloedt worden door de onderlinge verhoudingen van de basen van DNA [24]. 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 DNA opeenvolging en samengesteld (richting 5’ naar 3’) en dat rechterbeeldlijn wordt gecodeerd in DNA, maar dan wordt bij deze het Watson-Crick complement samengesteld (richting 3’ naar 5’). Als beide DNA opeenvolgingen in een oplossing worden gedaan met enkele voorwaarden, zal dit leiden tot opeenvolgingen die gelijk zijn aan elkaar die zo een dubbel vastgelopen DNA vormen. Als gevolg van de algemene kruising zullen de ongelijkwaardige delen tot ‘bellen’ leiden en verder zullen de verschillende intensiteitwaarden niet gelijke gebieden vertegenwoordigen. Indien men de afbeelding van signaalwaarden op DNA moleculen zorgvuldig ontwerpt, kan het ontharden van DNA een krachtig hulpmiddel zijn. Gebruikmakend van DNA kan men een optimale oplossing vinden. Als men de lengte van elke bel opmeet en ook de positie van elke bel bepaalt in beide richtingen, dan verkrijgt men de gezochte ongelijkheidsramingen. Echter zijn deze procedures nog niet realiseerbaar met de huidige technieken.

7.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 signaal vergelijkingsprobleem zijn de onnauwkeurigheid van gelijkenissen en de aanwezigheid van ruis. Ruis is vaak onvermijdelijk en komt vooral uit het signaalvormingsproces, het transmissiemiddel, het opnameprocédé of een combinatie van deze drie. Kortom om het passende probleem op te lossen, is het noodzakelijk om de gelijkenissen tussen signalen te kwantificeren. Digitale signalen moeten eerst in de opeenvolging 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 [25,26]. NTC geeft geen oplossing voor het codewoordontwerp, maar geeft slechts een verband tussen gehele waarden en het smeltpunt van DNA opeenvolgingen. Als gevolg van deze beperking moeten duplexen, gevormd door codewoorden toegewezen aan naburige signaalwaarden, een hoog smeltpunt hebben, terwijl duplexen die niet in deze buurt zijn, een smeltpunt lager moeten hebben dan een bepaalde drempelwaarde.

7.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. Polymerase kettingreactie (PCR), al behandeld bij de operaties, is een handige manier om gegevensbestanden te repliceren en het opvragen van gegevensbestanden kan op allerlei manieren plaatsvinden. Als men vraagmoleculen krijgt, kan met behulp van ontharden van DNA een zeer efficiënte manier geboden worden voor het

zoeken naar gelijkwaardige moleculen in het gegevensbestand, dit in tegenstelling tot digitale gegevensbestanden. Bij het gebruik van ontharden van DNA als zoekmechanisme is de vraagtijd niet afhankelijk van de grootte van het gegevensbestand, omdat de kinetica van DNA van relatieve concentraties afhankelijk is en niet van het aantal verschillende moleculen.

7.4.

Praktische toepasbaarheid

We hebben het gelijkheidsprobleem beschreven als illustratie hoe gegevensverwerking van DNA op DSP problemen toegepast kan worden. Op DNA gebaseerde DSP problemen vereisen het ontwerp van een nieuw coderingsschema, dat een oplossing kunnen vinden voor onvolmaakte gelijkenissen en de aanwezigheid van ruis. Hierdoor is de term NTC opgedoken en de voordelen hiervan worden besproken. DNA gegevensbestanden van digitale signaalgegevens werden voorgesteld als directe toepassing van NTC. De voordelen van het gebruik van DNA om gegevens digitaal op te slaan, voornamelijk signalen, omvat: informatie compactheid, economisch replicatie van gegevensbestanden, efficiënte vraagmechanismen en een vraagtijd, die onafhankelijk is van de grootte van het gegevensbestand. Om deze redenen is het gebruik van DNA als opslagmiddel een goede kandidaat vergeleken met magnetische opslagmiddelen. Hoewel de technologie nu nog beperkt is, is er hoop dat er een nieuwe discipline ontstaat, te weten dat van op DNA gebaseerde digitaal signaalverwerking.

8. Conclusie Er wordt vooruitstrevend onderzoek gevoerd naar de mogelijkheden van DNA computing, maar daarbij werd in mindere mate de praktische toepasbaarheid in ogenschouw genomen. Dit artikel heeft op verschillende toepassingsgebieden de praktische kant van DNA computing onderzocht. Om praktische informaticatoepassingen te implementeren zijn er verschillende hulpmiddelen nodig. Ten eerste is het nodig 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 met betrekking tot opslagcapaciteit. Het is alleen niet praktisch toepasbaar als snelle toegangstijden vereist zijn. Dit sluit dus alle interactieve applicaties uit. Een tweede vereiste is het uitvoeren van aritmetische operaties of een vorm van programmeren. We hebben geconcludeerd dat het mogelijk is om alle operaties die op een conventionele computer uitvoerbaar zijn, ook mogelijk zijn op een DNA computer. DNA computing biedt wel voordelen bij een speciale vorm van informatieverwerking, namelijk parallelle verwerking. Omdat DNA operaties parallel uitgevoerd kunnen worden, zijn moeilijk oplosbare problemen beter schaalbaar. Er is echter nog veel onderzoek nodig naar snellere methodes voor DNA manipulatie voordat het praktisch toepasbaar wordt. Cryptografie en signaalverwerking zijn beiden specifieke toepassingen die zowel parallelle verwerking, informatieopslag en DNA operaties gebruiken. De hierboven getrokken conclusies gelden dus ook voor deze specifieke toepassingen. Ook kan gesteld worden dat het bij cryptografie praktisch toepasbaar is als de snelheid niet van belang is. Concluderend kan er gesteld worden dat DNA computing zeer veel potentie heeft. De grote bottleneck wordt gevormd door de trage methodes voor DNA manipulatie. Zodra deze methodes sneller worden gemaakt is er niets dat DNA computing van een rooskleurige toekomst weerhoudt. Op dit gebied wordt nog steeds veel onderzoek uitgevoerd. De toekomst DNA computing is dus voorlopig afhankelijk van de vorderingen in de biochemie.

References [1] D. Boneh, C. Dunworth, R. Lipton. Breaking DES using a molecular computer, In Eric B. Baum and Richard J. Lipton, editors, DNA Based Computers, volume 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996. [2] N. Pisanti. A survey on DNA-Computing, Universita di Pisa Departimento di Informatica, 1997 [3] D. Rooβ and K. W. Wagner. On the power of DNA Computing, Academic Press, 1996 [4] L. M. Adleman. Molecular Computation of Solutions to Combinatorial Problems, Institute for Molecular Medicine and Technology, University of Southern California, 1994 [5] R. J. Lipton. Using DNA to solve NP-complete problem, Technical report, Princeton University, USA, 1995 [6] Lila Kari. DNA Computing: arrival of biological mathematics,1997. [7] Peterson, Ivars. Ivars Peterson's MathLand: DNA adds up. Juli, 1996 [8] Z. Frank Qiu, Mi Lu. A new solution for Boolean Circuit with DNA Computer.April 2000. [9] F. Guarnieri, M. Fliss, C. Bancroft. Making DNA add. 1996. [10] C. Taylor Clelland, V. Risca and C. Bancroft. Hiding messages in DNA microdots. Nature, 399:533-534, 1999. [11] E. Baum. Building an Associative Memory Vastly Larger Than the Brain. Science, 268:583-585, 1995. [12] J. Reif, T. LaBean, M. Pirrung, V. Rana, B. Guo, C. Kingsford and G. Wickham. Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability. In DNA Computing, 7th international Workshop on DNA-Based Computers, DNA 2001, Tampa, U.S.A., 10-13 June 2001, pages 241-250, 231-247. University of South Florida, 2001. [13] I. Katsányi. On Implementing Relational Databases on DNA Strands. Acta Cybernetica, 16(2):231-247, 2002. [14] P. Chung Wong, K. Wong and H. Foote. Organic Data Memory using the DNA Approach. Communications of the ACM, 46(1):95-98, 2003. [15] M. Ogihara, A. Ray, Executing parallel logical operations with DNA, 1999 [16] H. Hug, R. Schuer, DNA-based parallel computation of simple arithmetic, Juli 2001 [17] K. Li. Massively Parallel Biological Computing, NP-Complete, Volume 4 nummer 1 1996 [18] J. H. Reif, Paradigms for Biomolecular Computation, 1998. [19] A. Tanenbaum. Computer networks. Addison-Wesley, Reading, MA, 1985. [20] Gehani, A., LaBean, T.H., and Reif, J.H. 1999. DNA-based Cryptography. 5th DIMACS workshop on DNA Based Computers, MIT, June, 1999. [21] Michael J. Wiener. 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, pp. 31-79 (1996).

[22] R.M. Haralick and L.G. Shapiro, “Image matching,” in Computer and Robot Vision. Reading MA: Addison-Wesley, vol. II, Ch. 16, 1993. [23] A.P. Mills, B. Yurke, and P.M. Platzman, “Article for analog vector algebra computation,” Biosystems, vol. 52, no. 1-3, pp. 175–180, 1999. [24] N. Peyret, P.A. Seneviratne, H.T. Allawi, and J. SantaLucia, Jr., “Nearest-neighbor thermodynamics and NMR of DNA sequences with internal A-A, C-C, G-G, and T-T mismatches,” Biochemistry, vol. 38, no. 12, pp. 3468–3477, 1999. [25] S.A. Tsaftaris, “DNA-based digital signal processing,” M.S. thesis, Northwestern Univ., Dept. Elec. Computer Eng., 2003. [26] S.A. Tsaftaris, A.K. Katsaggelos, T.N. Pappas, and E.T. Papoutsakis, “DNA based matching of digital signals,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol. 5, Montreal, Quebec, Canada, May 17–21, 2004, pp. 581–584. [27] E. Winfree, “On the computational power of DNA annealing and ligation,” in DNA Based Computers: Proc. DIMACS Workshop, April 4, 1995, pp. 199–221.