Sankoff-Algorithmus

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

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\le i<j\le m,0\le i^{\prime }<j^{\prime }\le n$, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

$M[i,j,i^{\prime },j^{\prime }]=\left\{\begin{array}{cc}\mathrm{match}(u_i,v_{i^{\prime }},M[i+1,j,i^{\prime }+1,j^{\prime }])& \\ \mathrm{ins}(v_{i^{\prime }},M[i,j,i^{\prime }+1,j^{\prime }])& \\ \mathrm{del}(u_i,M[i+1,j,i^{\prime },j^{\prime }])& \\ \mathrm{pmatch}(u_i,u_k,v_{i^{\prime }},v_{k^{\prime }},M[i+1,k,i^{\prime }+1,k^{\prime }],M[k+1,j,k^{\prime }+1,j^{\prime }])& ,i\le k\le j\\ & ,i^{\prime }\le k^{\prime }\le j^{\prime }\end{array}\right\}$

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 \{|u|,|v|\}$.

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^{\prime }$ betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf $O(n^{4}c)$.

Literatur

• Vorlage:Literatur