Sankoff-Algorithmus
# 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})$.

## 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)$.