DNA - Computing

DNA - ComputingDNA - Computing

Seminar 2001

Institut Wissenschaftliches Rechnen

TU Braunschweig

ÜberblickÜberblick

Historische EntwicklungBiologische GrundlagenHamilton Path Problem (HPP)Kombinatorische DNA – Lösung des HPPModelle von DNA-ComputingNanostrukturen der DNA Ausblick

EinführungEinführung

1993 Adleman lernt die Grundlagen der Molekularbiologie

1994 Adleman löst das HPP mit Hilfe von DNA 1994 Publizierung seiner Ergebnisse 1995 Formalisierung des ersten Modells durch

Lipton Heute Breite Forschung mit weltweiten

Konferenzen

Biologische GrundlagenBiologische Grundlagen

• DNA als Informationsspeicher des DNA-Computers

• Operationen eines DNA-Computer

• Informationen kodieren• schreiben• lesen• manipulieren

D N AD N A• 1944 von Avery entdeckt• Gundbaustein der Natur• besteht aus einzelnen Nukleotiden (Oligonukleotide)

• Zucker (desoxyribose)• Phosphatgruppe• Base

Detaillierter Aufbau eines Detaillierter Aufbau eines NukleotidsNukleotids

D N AD N AModell der DNA• -Doppelhelix• strickleiterartiger Doppelstrang aus gleichlangen Polynukliotidketten

5‘ 3‘

5‘3‘

DNA als InformationsträgerDNA als Informationsträger

• herkömmliche Computer haben Alphabet X = {0, 1} • DNA besitzt Alphabet X‘ = {A, T, G, C}

Die DNA eines Menschen umfasst 6 Milliarden Basenpaarewas einer Information von ca. 500 Büchern mit 1500 Seiten entspricht.

Amplifying (Replikation)Amplifying (Replikation)

Annealing / MeltingAnnealing / Melting

Melting(erhitzen)

Annealing(abkühlen)

SynthesizingSynthesizing

CuttingCutting

SeparatingSeparating

ExtractingExtracting

SubstitutingSubstituting

Detecting / ReadingDetecting / Reading• Verwendung von PCR / Gelelektophorese• Einsatz von Blockmitteln bei der PCR• daraus resultieren kleinere Einzelstränge, die mit dem Hauptstrang zusammenhängen• durch veränderte Gelelektrophorese werden Positionen bestimmt

Neuere Methoden verwenden Leuchtstofffärbungen statt der PCR, die bei der Gelelektrophorese erkannt werden.

...weitere Operationen...weitere Operationen

• Mixing (Crossover)• Ligating (Konkatenation)• Marking / Unmarking• Destroying (Exonuclease Enzyme)

„„Ein DNA-Programm“Ein DNA-Programm“

• Gefäß mit in DNA kodierter Eingabe• ...Synthesizing...• ...Marking...• ...Ligating...• ...Reading...• ...• Ausgabe durch Detection als true / false oder wieder durch DNA kodiert

Hamilton Path ProblemHamilton Path Problem

Gegeben: Ein gerichteter Graph, ein Start- und ein Endknoten

Gesucht: Ein Pfad vom Start- bis zum Endknoten, wobei jeder Knoten genau einmal besucht werden muß.

42

71

36

5

Richtiger Weg:1326547

Lösen des HPP Lösen des HPP

1. Erzeuge eine Menge von zufällig bestimmten Pfaden durch den Graphen

2. Für alle Pfade in dieser Menge:a. Beginnt der Pfad mit dem Startknoten und endet mit

dem Endknoten ?b. Enthält der Pfad genau |V| Knoten ?c. Sind alle Knoten im Pfad vorhanden?

3. Alle Pfade in der verbleibenden Menge sind Lösungswege, ist die Menge leer gibt es keine Lösung.

Umsetzung des Algorithmus Umsetzung des Algorithmus mit DNA - Sequenzenmit DNA - Sequenzen

Kodierung der Knoten und Kanten als DNA-Sequenzen durch Synthetisierung

Länge der Sequenzen jeweils 20 BasenJeder Knoten und jede Kante eindeutig

Knoten und KantenKnoten und Kanten

TCAGGTCGAG TCAGGTCGAG GCCTACGTAG GCCTACGTAG

Knoten A Knoten B

AGTCCAGCTC CGGATGCATC

Kante A B

Komplement

Erzeugung aller PfadeErzeugung aller Pfade

TGAATCGACTTCCGATAGCT

TGAACTGGGATCTAGCTAGC

1014 Moleküle

0,9 % NaCL0,9 % NaCL

100 Mikroliter Kochsalzlösung

= TT-100

Erzeugung aller Pfade IIErzeugung aller Pfade II

• Hybridisierung von Knoten und Kanten• Ligation, zur Verstärkung des Rückrats der DNA

Ausfilterung der Pfade ohne Ausfilterung der Pfade ohne richtigen Start- und Endknotenrichtigen Start- und Endknoten

• Melting Trennung der Doppelhelix• Hinzugabe von Sequenzen der Start- und Endknoten als Primer• DNA-Polymerase vermehrt die DNA-Sequenzen unterschiedlich:

• Mit Start- und Endknoten exponentiell• Mit Start- oder Endknoten verdoppelt• Mit keiner Entsprechung gar nicht

• Nach mehren Zyklen des Erwärmens, Abkühlens und Vermehrens wird eine Probe entnommen, die jetzt fast nur noch Pfade einen richtigen Start- und Zielknoten enthält.

Kontrolle der LängeKontrolle der Länge

• Ein richtiger Pfad muß genau 140 bp (=Basenpaare) lang sein 7 Knoten a‘ 20 Basenpaaren• DNA-Sequenzen laufen elektrophoretisch über ein Agarose-Gel

Überprüfung der Existenz Überprüfung der Existenz jeden Knotensjeden Knotens

•Wiederholung für alle Knoten mit entsprechenden Sonden •Melting, damit DNA-Einzelstränge vorliegen• Einbringung von Eisensonden mit Komplementstrang eines Knoten• Durch Anbringung eines Magneten bleiben alle Moleküle haften, die diesen Knoten enthalten• Abgießen der Lösung und neue Lösung ansetzen• Melting trennt Stränge von Sonden• Abgießen der Lösung in ein neues Reagenzglas

Falls noch DNA vorhanden ist, muß das die Lösung des Problems Falls noch DNA vorhanden ist, muß das die Lösung des Problems sein.sein.

Eisensonden mit DNA-Eisensonden mit DNA-SequenzenSequenzen

Sonden-DNA

Eisenkugel

Enthaltener Knoten

Nicht passende DNA

RückblickRückblick

Alle Pfade

Alle Pfade mit vS und vE

Alle Pfade mit der Länge |V|

Knoten 1 enthalten

Knoten 2 enthalten

Knoten n enthalten =Lösungsmenge

Fehler beim DNA-ComputingFehler beim DNA-Computing

Pfad wird nicht erzeugtOperationen arbeiten nicht fehlerfrei

Falsche Lösungen bleiben erhaltenFehlerursache Größe, Menge und Masse der DNA

Nur statistisch wahrscheinliche Lösung !

Beschränktes ModellBeschränktes Modell

DNA-Menge nimmt in der Berechnungsphase nicht mehr zu

DNA-Menge ist in der Initialisierungsphasebeschränkt

Anwendung von PCR wird ausgeschlossen

Beschränktes ModellBeschränktes ModellBitvektoren kodierende Sequenzen werden erzeugt.

....A0

A1 A2 An-1

An

X0=1

X0=0

X1=1

X1=0

Xn-1=1

Xn-1=0

Vorteil: Wiederverwendung der Bitstrings für andere Probleme

Beschränktes ModellBeschränktes ModellOperationenOperationen

ExtractionSequenzen werden getrennt, abhängig obSubsequenz vorhanden

MergeVereinigung zweier Mengen von DNA

DetectionTest, ob DNA überhaupt noch vorhanden

Unbeschränktes ModellUnbeschränktes Modell

Erweiterung des beschränkten Modellesdurch Adleman

Menge der DNA darf zunehmenErweiterte Operation:

Amplify (PCR)

Generator-ModellGenerator-Modell

Initialisierungsmenge effizienter nutzenSuchraum einschränken

Generator-ModellGenerator-ModellOperationenOperationen

• Split Zufällige Aufteilung der DNA-Menge in zwei Mengen• Append Verlängerung der Sequenzen um Sequenzteile• Merge Vereinigung von zwei DNA-Mengen

Iteratives Anwenden von Split - Append - Merge erzeugt zufällige Bitvektoren. Wenn Split - Merge an bestimmten Positionen wegge-lassen wird, haben alle Sequenzen an der Stelle die gleiche Bitbelegung.Der Suchraum hat eine Dimension weniger.

Surface-ModellSurface-Modell

DNA-Sequenzen fixiert auf einer OberflächeBessere KontrolleEinengung des Suchraums

Modell wird verwendet, um Erkenntnisse überOperationen und deren Fehler zu gewinnen

Nanostrukturen von DNANanostrukturen von DNA

DNA-Cube

Nanostrukturen von DNANanostrukturen von DNA

• Watson-Crick komplementär bildet Doppelhelix

• eine Zelle bildet verschiedene geometrische Gebilde

• Verhalten der Kreuzung ist vorhersagbar

• Oligonukleotide bis hin zu Superstrukturen können zur Realisierung verschiedener Rechenmodelle benutzt werden

Nanostrukturen von DNANanostrukturen von DNA

• „self-assembly“ DNA

• kleine Anzahl von Oligonukleotiden bildet self-assembled DNA-Stränge

• self-assembly entspricht gewissen Regeln

„„self-assembly“ - Einsatzself-assembly“ - Einsatz

Durch die Definition verschiedene Operationen auf den verschiedenen Strukturen kann folgender Einsatz erreicht werden• linear doppelte DNA-Sequenz entspricht regulärer Sprache• self-assembled verzweigte DNA kann kontextfreie Sprachen erzeugen• doppelte Crossover-Moleküle sind geeignet für universelle Berechnungen

„„small Bricks“small Bricks“

T A ET A E

Triple Doppelhelix mit anti-parallelen Überkreuzungen und einer geraden Anzahl von Halbdrehungen

T A OT A O

Geeignet für Xor - Funktion / Integer - Addition

D A ED A E

Geeignet für Integer - Addition / Lösen des HPP

X

Y

Z

W

Im folgenden Gebrauch schematisch dargestellt als:

Ein-/Ausgabe mit Ein-/Ausgabe mit NanostrukturenNanostrukturen

„„Adleman Graph“Adleman Graph“

65

71

42

3

Ablauf des AlgorithmusAblauf des Algorithmus

• Erzeugen aller Pfade von Knotenpunkt 1 zu Knotenpunkt N.

• Sortieren der Knoten in jedem Pfad in ansteigender Ordnung.

•Kontrolle für jeden Pfad, dass das Resultat genau “1,2, 3,...N” ist.

• Ausgabe jedes Weges, der den Test erfüllt, wenn es einen gibt.

Erzeugen aller PfadeErzeugen aller Pfade

SortierenSortieren

Sortieren der einzelnen „Reihen“ durch „Odd-Even-Transposition Sort“

Komplettieren der StrukturKomplettieren der Struktur

• Einfügen spezieller End - Einheiten• „DONE“ kann die Struktur in den Finalzustand überführen

BeispielergebnisseBeispielergebnisse

Gültiger Hamilton-Pfad (1,4,5,2,3,6,7)

BeispielergebnisseBeispielergebnisse

Ungültiger Pfad (1,2,3,4,5,2,3,6,7)

Vergleich der AlgorithmenVergleich der Algorithmen

Adleman:• N (Nodes) + E (Edges) Oligonukleotide• N Laborschritte (durch Separating)

„self-assembled“:• E² / N + N² + N DAE Einheiten• konstante Anzahl von Laborschritten (Synthesizing, Annealing, Sequenzing)

Ausblick und BewertungAusblick und BewertungVorteileVorteile

Hohe Parallelität der Berechnung– Maximum 270 DNA-Stränge in einem

Reagenzglas

Hohe Energieeffizienz – 1 Joule schafft 2*1019 Operationen

Geringer Platzbedarf– 1 Bit braucht 1nm³

Ausblick und BewertungAusblick und BewertungNachteileNachteile

Viele Operationen sind zeitaufwendig– insbesondere Ein- und Ausgabe

NP-Probleme bleiben immer noch NP-Probleme

Operationen können fehlerhaft seinStatistisches VerfahrenKostenaufwendig

Ausblick und BewertungAusblick und Bewertung

Interessant für Forschung und Technik (Medizin).Evolutionäre Algorithmen...

DNA-Computer werden in den nächsten 40 Jahrenvon-Neumann-Rechner für den Home-User nicht ablösen.

The EndThe End

Viel Spaß auf dem Sportfest....Viel Spaß auf dem Sportfest....

...PROST....PROST.