Sankoff-Algorithmus

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

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(n⁶) und der Speicherbedarf in O(n⁴).

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'<j'\le n$, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

$M[i,j,i',j'] = \begin{Bmatrix} match(u_i, v_{i'}, M[i+1,j,i'+1,j']) & \\ ins(v_{i'}, M[i,j,i'+1,j']) &\\ del(u_{i}, M[i+1,j,i',j']) &\\ pmatch(u_i, u_k, v_{i'}, v_{k'}, M[i,k,i',k'], M[k,j,k',i]) & ,i\le k\le j \\ & , i'\le k'\le 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( | u | , | v | ).

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

Der Speicherbedarf ist in O(n⁴), da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.

Varianten

Da O(n⁶) 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⁴c).

Literatur

• David Sankoff: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. In: SIAM Journal on Applied Mathematics. 45, Nr. 5, Oktober 1985, S. 68-82.