Sankoff-Algorithmus
Der Sankoff-Algorithmus nutzt dynamische Programmierung in der Genetik, um simultan die drei Teilprobleme Sequenzalignment, Proteinfaltung und Phylogenie zu lösen. Er faltet und aligniert zugleich zwei Nukleotidsequenzen, so dass unter einem Energie-Modell die freie Energie der Sekundärstrukturen und die Kosten der Editierungsoperationen des Alignments minimiert werden. Die Laufzeit des Algorithmus ist in O<math>(n^6)</math> und der Speicherbedarf in <math>O(n^4)</math>.
Fallunterscheidung
Die Rekurrenzen des Algorithmus implementieren grundlegend folgende Fallunterscheidung:
1. Ein Match von zwei Basen
2. Eine Insertion einer Base
3. Eine Deletion einer Base
4. Ein Match von zwei Basenpaaren.
Seien die beiden Eingabesequenzen <math>u,v</math>, mit <math>m = |u|, n = |v|</math> und <math>0\le i<j\le m, 0\le i'<j'\le n</math>, dann ist die vereinfachte Grundstruktur der Rekurrenzen:
<math>M[i,j,i',j'] = \begin{Bmatrix} \operatorname{match}(u_i, v_{i'}, M[i+1,j,i'+1,j']) & \\ \operatorname{ins}(v_{i'}, M[i,j,i'+1,j']) &\\ \operatorname{del}(u_{i}, M[i+1,j,i',j']) &\\ \operatorname{pmatch}(u_i, u_k, v_{i'}, v_{k'}, M[i+1,k,i'+1,k'], M[k+1,j,k'+1,j']) & ,i\le k\le j \\
& , i'\le k'\le j' \\
\end{Bmatrix} </math>
Fall 4 stellt sicher, dass bei gleichzeitiger Faltung beide Strukturen die gleiche Anzahl und Schachtelung von Hairpins bilden.
Komplexität
Sei die Eingabe zwei Sequenzen <math>u,v</math>, mit <math>n = \max\left\{|u|, |v|\right\}</math>.
Die Laufzeit liegt in <math>O(n^6)</math>. Für alle <math>O(n^2)</math> Teilwörter von <math>u</math> müssen alle <math>O(n^2)</math> Teilwörter von <math>v</math> und in jeder Fallunterscheidung zwei Grenzen, die jeweils in <math>O(n)</math> variieren, betrachtet werden.
Der Speicherbedarf ist in <math>O(n^4)</math>, da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.
Varianten
Da <math>O(n^6)</math> Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in der Fallunterscheidung nicht alle möglichen <math>k</math> bzw. <math>k'</math> betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf <math>O(n^4 c)</math>.
Literatur
- David Sankoff: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. In: SIAM Journal on Applied Mathematics. Band 45, Nr. 5, Oktober 1985, S. 68–82.