In 2011 I wrote my bachelor thesis about DNAQL and I created a simulator for it at the university of Hasselt. My promoter was professor Jan Van den Bussche and my mentor was Joris Gillis. DNAQL is a formal model for databases in DNA and thus belongs to the domain of DNA Computing. The main purpose of this thesis was firstly to write a general (and understandable) introduction to DNA Computing and the DNAQL model, and secondly to develop a DNAQL simulator to perform virtual DNA(QL) experiments.

My bachelor’s thesis is written in Dutch. The first part is more like a general introduction to DNA and DNA Computing. The second part is specifically about the formal model DNAQL and its operations. The last part is about how I implemented the DNAQL simulator and how the simulator works. You can download the text here and here. I also gave a short presentation which is also available online. The binaries and the source code of the simulator aren’t available yet but maybe they will in the future.

I also wrote a short and easily readable article (in Dutch) that summarizes more or less my thesis. I’ve written the article to participate in the ‘Vlaamse scriptieprijs‘, a contest in Belgium. You can find it by following this link or by looking after the break.

Show the article... »

Bewaar je databank in de diepvries

Figuren en bibliografie

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!