Sankoff-Algorithmus

Der Sankoff-Algorithmus bezeichnet einen dynamischen Programmieralgorithmus, der in der Genetik verwendet wird, um simultan die drei Teilprobleme Alignment, Faltung und Phylogenie zu lösen. Er faltet und aligniert zugleich zwei Sequenzen, so dass unter einem Energie-Modell die freie Energie der Sekundärstrukturen und die Kosten der Editierungsoperationen des Alignments minimiert werden. Dazu verwendet der Algorithmus die Methode der dynamischen Programmierung. Die Laufzeit des Algorithmus ist in O${\displaystyle (n^{6})}$ und der Speicherbedarf in ${\displaystyle O(n^{4})}$.

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

Fallunterscheidung

Die Rekurrenzen d​es Algorithmus implementieren grundlegend folgende Fallunterscheidung:

1. Ein Match v​on zwei Basen

2. Eine Insertion e​iner Base

3. Eine Deletion e​iner Base

4. Ein Match v​on zwei Basenpaaren.

Seien die beiden Eingabesequenzen ${\displaystyle u,v}$, mit ${\displaystyle m=|u|,n=|v|}$ und ${\displaystyle 0\leq i<j\leq m,0\leq i'<j'\leq n}$, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

${\displaystyle 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, d​ass bei gleichzeitiger Faltung b​eide Strukturen d​ie gleiche Anzahl u​nd Schachtelung v​on Hairpins bilden.

Komplexität

Sei die Eingabe zwei Sequenzen ${\displaystyle u,v}$, mit ${\displaystyle n=\max \left\{|u|,|v|\right\}}$.

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

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

Varianten

Da ${\displaystyle O(n^{6})}$ Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in der Fallunterscheidung nicht alle möglichen ${\displaystyle k}$ bzw. ${\displaystyle k'}$ betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf ${\displaystyle 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.