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$(n^{6})$ und der Speicherbedarf in $O(n^{4})$.

Eine RNA-Sekundärstruktur, d. h. eine Faltung einer RNA-Sequenz.

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 $u,v$, mit $m=|u|,n=|v|$ und $0\leq i<j\leq m,0\leq i'<j'\leq n$, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

$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\leq k\leq j\\&,i'\leq k'\leq j'\\\end{Bmatrix}}$

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 $u,v$, mit $n=\max \left\{|u|,|v|\right\}$.

Die Laufzeit liegt in $O(n^{6})$. Für alle $O(n^{2})$ Teilwörter von $u$ müssen alle $O(n^{2})$ Teilwörter von $v$ und in jeder Fallunterscheidung zwei Grenzen, die jeweils in $O(n)$ variieren, betrachtet werden.

Der Speicherbedarf ist in $O(n^{4})$, da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.

Varianten

Da $O(n^{6})$ Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in der Fallunterscheidung nicht alle möglichen $k$ bzw. $k'$ betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf $O(n^{4}c)$.

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.