DNAQL Simulator Presentatie Bachelorproef
Tom Desair Universiteit Hasselt
Academiejaar 2010 - 2011
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
1 / 13
Inleiding
Inhoud
Inhoud 1
Inleiding Inhoud Het onderwerp
2
Databases in DNA De DNA molecule Motivatie
3
Het Sticker Complex Datamodel Sticker Complexen Operaties en DNAQL
4
Implementatie Datastructuren en Algoritmen Demo
5
Vragen
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
2 / 13
Inleiding
Het onderwerp
Onderwerp bachelorproef
1
Het beschrijven van een theoretische data(base) model dat gebruik maakt van DNA Structuur en processen van DNA DNA Computing
2
Het implementeren van een interpreter/simulator van dit model Resultaat: DNAQL Simulator Computermodellen, geen echte DNA moleculen
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
3 / 13
Inleiding
Het onderwerp
Onderwerp bachelorproef
1
Het beschrijven van een theoretische data(base) model dat gebruik maakt van DNA Structuur en processen van DNA DNA Computing
2
Het implementeren van een interpreter/simulator van dit model Resultaat: DNAQL Simulator Computermodellen, geen echte DNA moleculen
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
3 / 13
Databases in DNA
De DNA molecule
Desoxyribonucle¨ınezuur
Een molecule in de kern van elke cel (de chromosomen) Drager van genetische (overerfbare) eigenschappen Bepaalt mee de gehele werking van een organisme Basenparing: A − T en C − G Figuur: Structuur DNA molecule
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
4 / 13
Databases in DNA
Motivatie
Waarom data opslaan in DNA? DNA is een ideaal medium om data op te slaan Zeer klein (slechts enkele moleculen) Enorm robuust: opwarmen, bevriezen, schokbestendig. . . Relatief makkelijk aan te maken en in te lezen
Met DNA kunnen we ook berekeningen uitvoeren Operaties kunnen op duizenden moleculen in parallel werken Handig voor bulk data processing
Er zijn reeds verschillende experimenten gedaan DNA Computing Zelfs modellen die Turing-Compleet zijn
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
5 / 13
Databases in DNA
Motivatie
Waarom data opslaan in DNA? DNA is een ideaal medium om data op te slaan Zeer klein (slechts enkele moleculen) Enorm robuust: opwarmen, bevriezen, schokbestendig. . . Relatief makkelijk aan te maken en in te lezen
Met DNA kunnen we ook berekeningen uitvoeren Operaties kunnen op duizenden moleculen in parallel werken Handig voor bulk data processing
Er zijn reeds verschillende experimenten gedaan DNA Computing Zelfs modellen die Turing-Compleet zijn
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
5 / 13
Het Sticker Complex Datamodel
Sticker Complexen
Databases + DNA = ? Het sticker complex datamodel Ontwikkeld aan de Universiteit Hasselt Een sticker complex is een zes-tupel (V , E, λ, µ, immob, blocked) Definieert operaties op sticker complexen Union, Difference, Ligate, Hybridize, Split. . .
V W W
X
U
U
Z
Z
Y Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
6 / 13
Het Sticker Complex Datamodel
Sticker Complexen
Sticker complexen ≈ DNA complexen Complementaire strengen zijn ‘stickers’ op de (positieve) strengen. D
A
B
A
B
Sticker complex:
D = CTGAACCCTG A = ACGTGCATCA B = GTTCACCGAA
DNA complex:
C T G A A C C C T G A C G T G C A T C AG T T C A C C G A A G A C T T GGG A C T G C A C G T A G T C A A G T GGC T T
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
7 / 13
Het Sticker Complex Datamodel
Sticker Complexen
Datarepresentatie: een intu¨ıtief voorbeeld Gebruik van alfabetten voor attributen (Ω), waarden (Λ) en ‘structuur’-symbolen (Θ = {#1 , #2 , #3 , #4 , #5 , #6 , #7 , #8 , #9 }): A 1 3
B 2 4
#2
A
#3
1
#4
#2
B
#3
2
#4
#2
A
#3
3
#4
#2
B
#3
4
#4
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
8 / 13
Het Sticker Complex Datamodel
Operaties en DNAQL
Sticker complex operaties en DNAQL DNAQL is een query-taal voor sticker complexen Functionele programmeertaal Gebruikt de operaties van het sticker complex datamodel Verschillende toevoegingen zoals for-lus, if-test, functies. . .
Een voorbeeldprogramma fun main ( e1 , e2 ) : = l e t x : = e2 i n l e t y : = e1 i n i f empty ( x ) then empty else i f empty ( y ) then empty else difference ( x , y )
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
9 / 13
Implementatie
Datastructuren en Algoritmen
Implementatie: DNAQL Simulator Tools: C++, de STL library en het Qt framework Datastructuren: De syntaxboom klassen (Flex, Bison) Klassen voor sticker complexen Symbol table, Visualizer, CommandLineParser. . . Algoritmen: Implementeren van de sticker complex operaties ¨ Hybridisatie algoritme niet erg efficient Bepalen eindigheid hybridisatie
Inlezen en uitschrijven van sticker complex bestanden Bestandsformaat zelf bepaald
Het visualiseren van sticker complexen (force directed graph drawing) ... Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
10 / 13
Implementatie
Datastructuren en Algoritmen
Implementatie: DNAQL Simulator Tools: C++, de STL library en het Qt framework Datastructuren: De syntaxboom klassen (Flex, Bison) Klassen voor sticker complexen Symbol table, Visualizer, CommandLineParser. . . Algoritmen: Implementeren van de sticker complex operaties ¨ Hybridisatie algoritme niet erg efficient Bepalen eindigheid hybridisatie
Inlezen en uitschrijven van sticker complex bestanden Bestandsformaat zelf bepaald
Het visualiseren van sticker complexen (force directed graph drawing) ... Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
10 / 13
Implementatie
Demo
Demonstratie
En dan nu een demo. . .
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
11 / 13
Vragen
Vragen
Zijn er vragen?
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
12 / 13
Vragen
Bedankt
The End
Bedankt voor uw aandacht!
Tom Desair (Universiteit Hasselt)
DNAQL Simulator
Academiejaar 2010 - 2011
13 / 13
