18.05.2001
Thema: DNA-ComputingHamilton-Pfad-Problem
=====================
Gegeben ist ein gerichteter Graph G=(V,E),
|V| = n, |E| = m und 2 ausgez. Knoten s,t.
Gibt es einen Hamilton-Pfad von s nach t?
[ Anm:
[ Ein Hamilton-Pfad von s nach t ist ein Pfad,
[ bei dem jeder Knoten einmal passieret wird.
Das Problem ist NP-vollstîndig! Es wird vermutet, daœ es f½r solche
Probleme keine effiziente Lñsung gibt.
Ein einfacher Algorithmus zur Lñsung des Problems ist:
1. Erzeuge alle mñglichen Pfade von s nach t der Lînge (n-1),
die jeden Knoten einmal enthîlt.
==> Menge S
2. Teste ob zulîssige Pfade dabei sind.
(S nicht leer)
Komplexitît dieses Algorithmus: k*(n-2)!
F½r die Fakultît gibt es die Stirlingsche Approximation:
sqrt(2*PI*n) * (n/e)**n <= n! <= sqrt(2*PI*n) * (n/e)**(n+(1/(12*n)))
n! ~ (n/e)**n
[ Anm:
[ a**b heiœt "a hoch b"
[ e ist die Eulersche Zahl
Dieses Problem wird nun mit DNA-Computing gelñst:
Knotenreprîsentation: Knoten S_v ist 20 bp lange ssDNA
Kantenreprîsentation: siehe Anhang
Nun geht man folgendermaœen vor (Theorie):
1. Generate random paths.
2. From all paths created in the previous step, keep only those that
start at s and end at t.
3. From all remaining paths, keep only those that visit exactly n vertices.
4. From all remaining paths, keep only those that visit each vertex at
least once.
5. If any path remains, return yes; otherwise return no.
Die einzelnen Schritte werden jetzt einzeln erklîrt:
1.
I) - erzeuge n unterschiedliche, 20bp-lange ssDNA-Strînge S_v
- erzeuge komplementîre Strînge zu S_v durch PCR und vervielfîltige
im Reaktionsgefîœ T_1
II) - erzeuge alle gewollten mñglichen Kantenkombinationen durch
Schneiden
von Kanten S_v nach 10 bp und ligieren der unterschiedlichen Teile
in jeder mñglichen Kombination
- vervielfîltige Kanten durch PCR in T_2
III) - Gebe T_1 und T_2 zu T_3
==> Kanten und Knoten hybridisieren und werden ligiert
2. Man benutzt PCR mit Primern f½r S_s und dem Komplement zu S_t, um die
DNA-Strînge zu selektieren, die mit s starten und mit t enden => T_4
3. Mit T_4 f½hre Gel-Elektrophorese durch, die Strînge so auftrennt, daœ man
Strînge mit Lînge von 20*n bp erhîlt => T_5
4. Man nimmt ssDNA aus T_5 und selektiert iterativ f½r jeden Knoten v mit
Hilfe
von S_v nur solche Strînge aus, die an S_v hybridisieren.
In T_5:
For v element_von(V) do
T_5' := ssDNA aus T_5, die an S_v hybridisiert
T_5 := T_5'
[ Anm:
[ V = Menge aller Knoten
5. Gel-Elektrophorese mit T_5 ob ein ssDNA mit Lînge 20*n bp drin => true,
ansonsten false.