DNAQL Simulator

Tom Desair
Tom DesairBewaar je databank in de diepvriesWe leven in een tijdperk waarin we een exponentiële groei van opgeslagen data kennen. De sterke uitbreiding van het internet is hierbij één van de hoofdrolspelers. Zo wordt er op YouTube per minuut meer dan 48 uur beeldmateriaal geüpload (1), krijgt de fotodienst Flickr er elke dag 5 miljoen foto’s bij en worden er elke dag 140 miljoen berichten op Twitter geplaatst (2). Maar ook de technologische vooruitgang en de digitalisatie van steeds meer (oude) documenten dragen bij aan deze data-explosie.

DNAQL Simulator

Tom Desair

Bewaar je databank in de diepvries

We leven in een tijdperk waarin we een exponentiële groei van opgeslagen data kennen. De sterke uitbreiding van het internet is hierbij één van de hoofdrolspelers. Zo wordt er op YouTube per minuut meer dan 48 uur beeldmateriaal geüpload (1), krijgt de fotodienst Flickr er elke dag 5 miljoen foto’s bij en worden er elke dag 140 miljoen berichten op Twitter geplaatst (2). Maar ook de technologische vooruitgang en de digitalisatie van steeds meer (oude) documenten dragen bij aan deze data-explosie. Bovendien moeten veel gegevens lang en op een veilige manier bewaard worden. Een oplossing om de groeiende hoeveelheid data te bewaren, kan er uit bestaan de huidige computerchips nog sneller en kleiner te maken. Er staat echter een limiet op de kleinst mogelijke schaal waarop men computerchips kan produceren, een limiet die we bijna bereikt hebben (3). Daarenboven zijn de huidige harde schijven van computers niet echt robuust en betrouwbaar op lange termijn (4). De wetenschap is daarom op zoek naar een alternatieve gegevensdrager die gegevens voor een zeer lange periode kan bewaren, bijna niet breekbaar is en weinig ruimte in beslag neemt. Aan de Universiteit Hasselt werd een theoretische model ontwikkeld voor het opslaan en manipuleren van data met behulp van DNA-moleculen. De functie van deze moleculen is in de natuur immers ook het opslaan van onze erfelijke eigenschappen. Mijn bachelorproef, die ik heb afgelegd aan de School voor Informatietechnologie van de tUL (UHasselt) en waarover dit artikel gaat, bestond uit het ontwikkelen van een virtuele simulator voor dit theoretische model om het zo beter te kunnen onderzoeken.

Waarom zouden we DNA gebruiken en niet een ander opslagmedium? DNA is een molecule die zich in de kern van elke cel van ons lichaam bevindt. Ze bestaat uit twee ketens die opgebouwd zijn met slechts vier verschillende bouwstenen die we aanduiden met de letters A, C, G en T. Deze twee ketens zitten als een wenteltrap rond elkaar waarbij de tegenover elkaar liggende bouwstenen verbonden zijn en zo als het ware de treden van de trap vormen. Met behulp van deze vier bouwstenen beschrijft de molecule de overerfbare kenmerken van ons hele wezen. Als je dan bedenkt dat een volledige DNA molecule wel twee meter lang kan zijn, zie je dat DNA van nature al de eigenschap heeft om grote hoeveelheden data (onze erfelijke eigenschappen) te bewaren op een heel kleine schaal (de kern van een cel) (5). Bovendien is DNA enorm robuust. Denk maar aan een politieonderzoek waarbij in de meest extreme omstandigheden nog leesbaar DNA gevonden wordt. Zeker als men het DNA invriest, kan het vrijwel onbeperkt bewaard blijven. DNA heeft bovendien zijn mogelijkheden binnen de informatica reeds verschillende malen bewezen. Het eerste experiment waarbij DNA gebruikt werd voor het uitvoeren van een berekening, gebeurde reeds in 1994 (6)! Er is hierrond zelfs een heel onderzoeksdomein ontstaan, “DNA Computing” genaamd, dat zich bezighoudt met het uitvoeren van berekeningen met behulp van biologische moleculen (3). Een ander voordeel van berekeningen met DNA is dat ze op duizenden moleculen tegelijk worden toegepast waardoor er heel veel bewerkingen in parallel kunnen gebeuren. DNA is dus wel degelijk een geschikt alternatief opslagmedium.

Net zoals bij elke technologische vooruitgang, is er, voordat we een praktische toepassing kunnen ontwikkelen, eerst een hoop fundamenteel wetenschappelijk onderzoek nodig. Hiervoor ontwikkelde men aan de Universiteit Hasselt een theoretisch model dat als naam het “sticker complex datamodel” kreeg (7; 8). Het is een wiskundig model om DNA moleculen op een abstracte manier voor te stellen, wat we dan een “sticker complex” noemen. Er worden hierbij wel bepaalde beperkingen aan de moleculen opgelegd vooral omtrent ruimtelijke vorm en samenstelling. Het model deelt een DNA molecule op in verschillende blokken die grafisch worden voorgesteld door ‘pijlen’. Deze blokken kunnen in de lengte en/of de breedte met elkaar verbonden zijn. Elke pijl heeft ook een bijhorend symbool. Zo’n symbool vertegenwoordigt een bepaalde opeenvolging van bouwstenen in de DNA molecule (herinner je de wenteltrap). Zo kunnen we het abstracte model omzetten naar een werkelijke molecule. Dit is geïllustreerd in figuur 1 (een gestippelde boog duidt hier op een dubbele DNA keten).

Het sticker complex datamodel is voornamelijk bedoeld om tabellen van een databank in DNA te coderen. Hiervoor worden verschillende groepen van symbolen gebruikt. Zo hebben we een groep symbolen die de kolomnamen van een tabel voorstellen, een andere groep om veldwaarden te coderen en een laatste groep die de structuur van een rij in de tabel aangeeft. De symbolen van deze laatste groep beginnen typisch met een hekje. Met behulp van deze drie groepen kunnen we nu eenvoudig tabellen voorstellen in DNA. We construeren per rij een keten waarbij elke veldwaarde voorafgegaan wordt door zijn bijhorende kolomnaam, gescheiden door structuursymbolen. Dit is geïllustreerd in figuur 2 voor een tabel met de kolommen A en B. Het opslaan van data en tabellen is echter niet voldoende. De data moet ook nog makkelijk manipuleerbaar (het invoegen en verwijderen van data) en doorzoekbaar zijn. Om hieraan tegemoet te komen, werd de programmeertaal DNAQL ontwikkeld. Deze programmeertaal bevat de nodige functionaliteit om sticker complexen, en dus DNA moleculen, te manipuleren en hieruit nieuwe waarden te berekenen en dit op honderden moleculen tegelijkertijd. Dit maakt het sticker complex datamodel eveneens flexibel genoeg om ook voor andere doeleinden gebruikt te worden.

De kernopdracht van mijn bachelorproef was het ontwikkelen van een virtuele testomgeving die het mogelijk maakt om DNAQL programma’s uit te voeren op sticker complexen. De applicatie kreeg de naam “DNAQL Simulator”. Ik heb eveneens een grafische module ontwikkeld die de abstracte DNA moleculen op een zo optimaal mogelijke manier uittekent (zie figuur 3). Met behulp van deze applicatie kon ik twee zaken onderzoeken. Enerzijds ben ik nagegaan of de DNAQL programmeertaal en het sticker complex datamodel correct gedefinieerd zijn zodat ze hun doel kunnen bereiken. Anderzijds heb ik onderzocht welke operaties efficiënt simuleerbaar zijn en bij dewelke een simulatie niet altijd even vanzelfsprekend is. Bovendien is de DNAQL simulator uiterst geschikt om eventueel verder onderzoek te ondersteunen.

 

De simulator en de hiermee uitgevoerde tests brachten enkele onvolkomenheden en tegenstellingen in het sticker complex datamodel aan het licht. Hij werd ook getoond op de internationale DNA 17 conferentie over DNA Computing. Er blijft echter nog voldoende ruimte over voor verder onderzoek naar dit model: de efficiëntie van bepaalde operaties (en hun simulatie), de praktische realiseerbaarheid van het model, alternatieve toepassingen binnen DNA Computing… Allemaal vragen waarbij de gerealiseerde simulator kan helpen! 

 

De bibliografie en afbeeldingen waarvan melding wordt gemaakt kan je bekomen door een mailtje te sturen naar info at scriptieprijs punt be

Bibliografie

 [Adl94]    Leonard M. Adleman. Molecular computation of solutions to com-

           binatorial problems. Science, 266(5187):1021 – 1024, Nov 1994. [Amo05]    Martyn Amos. Theoretical and Experimental DNA Computation.           Springer, 2005. [Amo09]    Martyn Amos. DNA computing. In Robert A. Meyers, editor,           Encyclopedia of Complexity and Systems Science, volume 4, pages           2089 – 2104. Springer New York, 2009. http://www.doc.mmu.ac.           uk/STAFF/M.Amos/pubs.html. [Bal08]    Coco Ballantyne. Longest piece of synthetic DNA yet. Internet,           January 2008. http://www.scientificamerican.com/article.           cfm?id=longest-piece-of-dna-yet. [BETT98]   Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioan-           nis G. Tollis. Graph Drawing: Algorithms for the Visualization of           Graphs. Prentice Hall, 1998. [BGV11]    Robert Brijder, Joris J.M. Gillis, and Jan Van den Bussche. Graph-           theoretic formalization of hybridization in DNA sticker complexes.           Technical report, Hasselt University and transnational University           of Limburg, 2011. [BPEA+ 01] Yaakov Benenson, Tamar Paz-Elizur, Rivka Adar, Ehud Keinan,           Zvi Livneh, and Ehud Shapiro. Programmable and autonomous           computing machine made of biomolecules. Nature, 414(6862):430,           2001. [CRU+ 08]  Neil A. Campbell, Jane B. Reece, Lisa A. Urry, Michael L. Cain,           Steven A. Wasserman, Peter V. Minorsky, and Robert B. Jackson.           Biology. Pearson Benjamin Cummings, 8 edition, 2008. [dD87]     Christian de Duve. De levende cel, volume 10 of De Wetenschap-           pelijke Bibliotheek. Natuur & Techniek, 1987. [Dij11]    Arjen Dijkgraaf. DNA-sequenser op een chip. Mens & Molecule,           (2):25, February 2011. [Fey61]    Richard P. Feynman. There’s plenty of room at the bottom. In           D. Gilbert, editor, Miniaturization, pages 282 – 296. Reinhold Pu-           blishing Corporation, New York, 1961. [GHJV09]  Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.          Design Patterns Elements of Reusable Object-Oriented Software.          Addison Wesley professional computing series, 2009. [GV10]    Joris J.M. Gillis and Jan Van den Bussche. A formal model for          databases in DNA. Technical report, Hasselt University, 2010.          http://alpha.uhasselt.be/joris.gillis/pubs/anb10.pdf. [Kob05]   Stephen G. Kobourov. Force-directed drawing algorithms. In          Roberto Tamassia, editor, Handbook of Graph Drawing and Vi-          sualization. CRC Press, 2005. http://www.cs.brown.edu/~rt/          gdhandbook/chapters/force-directed.pdf. [LFDR87]  Marie Leblond-Francillard, Marc Dreyfus, and Francois Rougeon.          Isolation of DNA-protein complexes based on streptavidin and bi-          otin interaction. European Journal of Biochemistry, 166(2):351 –          355, 1987. [Mul90]   Kary B. Mullis. The unusual origin of the polymerase chain reac-          tion. Scientific American, 262(4):56 – 65, 1990. [OR96]    Mitsunori Ogihara and Animesh Ray. Simulating boolean circuits          on a DNA computer. In In Proceedings of 1st International Confe-          rence on Computational Molecular Biology, pages 326 – 331. ACM          Press, 1996. [QL00]    Liu Qinghua and Wang Liman. DNA computing on surfaces. Na-          ture, 403(6766):175 – 179, 2000. [QW11]    Lulu Qian and Erik Winfree. A simple DNA gate motif for          synthesizing large-scale circuits. J. R. Soc. Interface, Febru-          ary 2011. http://rsif.royalsocietypublishing.org/content/          early/2011/02/03/rsif.2010.0729.full. [Rei11]   John H. Reif. Scaling up DNA computation. Science, 332(6034):1156 – 1157, June 2011. [Rus10]   Peter J. Russell. iGenetics A Molecular Approach. Pearson Edu-          cation, third edition, 2010. International edition. [SG90]    Harold Swerdlow and Raymond Gesteland. Capillary gel electrop-          horesis for rapid, high resolution DNA sequencing. Nucleic Acids          Research, 18(6), 1990. [Sip06]   Michael Sipser. Introduction to the Theory of Computation. Course          Technology Cengage Learning, second edition, 2006. International          edition. [SKK+ 99] Kensaku Sakamoto, Daisuke Kiga, Ken Komiya, Hidetaka Gouzu,          Shigeyuki Yokoyama, Shuji Ikeda, Hiroshi Sugiyama, and Masami          Hagiya. State transitions by molecules. Biosystems, 52(1-3):81 –          91, 1999. [SSZW06]  Georg Seelig, David Soloveichik, David Yu Zhang, and Erik          Winfree.     Enzyme-free nucleic acid logic circuits.    Science,          314(5805):1585 – 1588, dec 2006. [Wri99]   Robert Wright. Watson & Crick. (cover story). Time, 153(12):172,          1999.