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