18.05.2001

Thema: DNA-Computing


Hamilton-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.