imported>Neutronstar2 am 3. Dezember 2023 um 20:14 Uhr

2023-12-03T20:14:00Z

Neue Seite

[[Datei:MOCO RNA motif secondary structure.jpg|200px|mini|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 [[Nukleotidsequenz]]en, so dass unter einem Energie-Modell die freie Energie der [[Sekundärstruktur]]en und die Kosten der Editierungsoperationen des Alignments minimiert werden. Die Laufzeit des Algorithmus ist in [[Landau-Symbol|O]]<math>(n^6)</math> und der Speicherbedarf in <math>O(n^4)</math>.

== Fallunterscheidung ==

Die Rekurrenzen des Algorithmus implementieren grundlegend folgende Fallunterscheidung:

1. Ein Match von zwei Basen

2. Eine [[Insertion (Genetik)|Insertion]] einer Base

3. Eine [[Deletion]] einer Base

4. Ein Match von zwei [[Basenpaar]]en.

Seien die beiden Eingabesequenzen <math>u,v</math>, mit <math>m = |u|, n = |v|</math> und <math>0\le i<j\le m, 0\le i'<j'\le n</math>, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

<math>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\le k\le j \\
& , i'\le k'\le j' \\
\end{Bmatrix}
</math>

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 <math>u,v</math>, mit <math>n = \max\left\{|u|, |v|\right\}</math>.

Die Laufzeit liegt in <math>O(n^6)</math>. Für alle <math>O(n^2)</math> Teilwörter von <math>u</math> müssen alle <math>O(n^2)</math> Teilwörter von <math>v</math> und in jeder Fallunterscheidung zwei Grenzen, die jeweils in <math>O(n)</math> variieren, betrachtet werden.

Der Speicherbedarf ist in <math>O(n^4)</math>, da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.

== Varianten ==

Da <math>O(n^6)</math> Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in
der Fallunterscheidung nicht alle möglichen <math>k</math> bzw. <math>k'</math> betrachten, sondern
beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf <math>O(n^4 c)</math>.

== Literatur ==
* {{Literatur |Autor=David Sankoff |Titel=Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems |Sammelwerk=SIAM Journal on Applied Mathematics |Band=45 |Nummer=5 |Datum=1985-10 |Seiten=68-82}}

[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Bioinformatik]]

Sankoff-Algorithmus - Versionsgeschichte

imported>Neutronstar2 am 3. Dezember 2023 um 20:14 Uhr