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 und der Speicherbedarf in .

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

Fallunterscheidung

Bearbeiten

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  , mit   und  , dann ist die vereinfachte Grundstruktur der Rekurrenzen:

 

Fall 4 stellt sicher, dass bei gleichzeitiger Faltung beide Strukturen die gleiche Anzahl und Schachtelung von Hairpins bilden.

Komplexität

Bearbeiten

Sei die Eingabe zwei Sequenzen  , mit  .

Die Laufzeit liegt in  . Für alle   Teilwörter von   müssen alle   Teilwörter von   und in jeder Fallunterscheidung zwei Grenzen, die jeweils in   variieren, betrachtet werden.

Der Speicherbedarf ist in  , da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.

Varianten

Bearbeiten

Da   Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in der Fallunterscheidung nicht alle möglichen   bzw.   betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf  .

Literatur

Bearbeiten
  • 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.