Nussinov-Algorithmus
Der Nussinov-Algorithmus ist ein einfacher Algorithmus zur Berechnung der maximal möglichen Anzahl von Basenpaaren in einer RNA-Sequenz und einer oder mehrerer möglicher Sekundärstrukturen dieser RNA-Sequenz. Wegen seiner einfachen Modell-Annahmen ist seine biologische Bedeutung gering, er wird aber in der Didaktik der Bioinformatik als einfaches Beispiel für dynamische Programmierung verwendet und dient als Ausgangspunkt für komplexere Modelle.
Algorithmus
Modell
Der Algorithmus modelliert eine RNA-Sequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} und die Basenpaare innerhalb dieser Sequenz als einen planaren Graphen, das heißt ohne Pseudoknoten. Zwischen den Basen eines einzigen Basenpaares liegt mindestens eine weitere Base, d. h., die Schleife einer Haarnadelstruktur besteht aus mindestens einer Base.
Gegeben ist die Sequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} der einzelnen Basen als eine Zeichenkette mit der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} . Dabei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i]} das Zeichen an der Stelle und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i .. j]} die Teil-Sequenz der Zeichen von der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} bis zur Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} . Damit ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i .. i]} gleichbedeutend mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i]} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[1 .. n]} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} . Weiters sei eine leere Zeichenkette der Länge 0.
![{\displaystyle s[i..i-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9de5ba85ca4bee6116e037e11568961ee300065a)
Die Matrix der Größe enthält die die Anzahl der maximal möglichen Basenpaare der Teilsequenzen für der Sequenz . Das Matrixelement bezeichnet dementsprechend die Anzahl der maximal möglichen Basenpaare für die gesamte Sequenz.
![{\displaystyle N[i,j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc3f50a38385d9c65e6a67e9be3cf3989c1be00)
![{\displaystyle s[i..j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebf63bf22305c7594ef2b27c8e639491a86fe7ac)
![{\displaystyle N[1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/493db03d387e62a2bec2d67f6e1ad74491ced2ed)
Die Funktion ergibt 1, wenn und komplementäre Basen sind, sonst 0.
![{\displaystyle s[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95c8024dbbc210b378cf497974e51129a7bd62b4)
![{\displaystyle s[j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60c5252fdedb32516342487b03fbf6654c12a1f1)
Pseudoknoten sind im Modell nicht erlaubt, d. h., für zwei Basenpaare und gilt oder
![{\displaystyle (s[a];s[b])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e57b4fb429e86be688662b208c8307635d5b5ed7)
![{\displaystyle (s[c];s[d])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d9be87b7a98ac42b9182d42a12accd2a721bf7f)
Zerlegung in kleinere Teil-Probleme
Die Elemente der Matrix werden berechnet, indem zuerst angenommen wird, alle Elemente bis auf das Element , das die Sequenz beschreibt, seien bekannt. Die Sequenz kann gebildet werden, indem der Sequenz die Base angehängt wird. Diese Base kann nun entweder mit einem anderen Element der Sequenz ein Basenpaar bilden oder nicht:
![{\displaystyle s[1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33860e142f40f3a925655ee6311439003a01f763)
![{\displaystyle s[1,n-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfde566a3a809a552d156ae1df880d676e673481)
![{\displaystyle s[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffe878c033cc70d1aa3ffbd156394791aa8dffde)
- Falls kein Basenpaar gebildet wird, so muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[1, n] = N[1, n-1]} sein und das Problem ist gelöst.
- Falls ein Basenpaar gebildet wird, so kann dieses Basenpaar zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[n]} und einer der Basen aus der Teil-Sequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[1 .. n-2]} gebildet werden. Angenommen, das Basenpaar bildet sich zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[k]} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[n]} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \le k \le n-2} so teilt sich die Sequenz in die weiteren Teile Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[1 .. k-1]} und . Für diese beiden Teile kann wiederum die Anzahl der maximal möglichen Basenpaare berechnet werden, indem der Algorithmus für diese Teile von Neuem begonnen wird. Die Summe der beiden Teile plus dem zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[k]} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[n]} gebildete Basenpaar ergibt einen möglichen Kandidaten-Wert für die Maximale Summe. Der Wert für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[1, n]} soll maximal werden, also muss für jedes erlaubte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \le k \le n-2} die Kandidaten berechnet werden. Der höchste so erreichbare Wert garantiert, dass auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[1, n]} maximal wird. Somit ist
![{\displaystyle s[k+1..n-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c712a08c09301bfc788c6b9ccb8aeb3f78174c0)
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[1, n] = \max \begin{Bmatrix} \max_{1<k<n-1} (N[1, k-1] + N[k+1, n-1] + 1) \cdot \sigma(k,n) & \\ N[2,n-1] \cdot \sigma(1,n) & \end{Bmatrix}}
und das Problem ist ebenfalls gelöst. Der untere Term der Maximalwertsberechnung behandelt den Sonderfall eines Basenpaares zwischen dem ersten und dem letzten Element der Sequenz, wodurch eine der Teilsequenzen leer ist (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[0,0]} ). Beide gelisteten Möglichkeiten werden überprüft und die höhere so erreichbare Anzahl an Basenpaaren ist das Ergebnis der Berechnung.
Der Algorithmus verkleinert die Sequenz auf diese Weise in immer kleinere Teil-Sequenzen, bis diese sofort berechnet werden können. Die Zwischenergebnisse werden dann zur Berechnung der nächstgrößeren Teil-Sequenzen verwendet.
Initialisierung
Die Teil-Sequenzen der Länge 2, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i,i]} der Länge 1 und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i,i-1]} der Länge 0 enthalten maximal 0 Basenpaare:
![{\displaystyle s[i,i+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39db6a7cdaf31bac04262262fe9975530c09a57a)
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i, i+1] = 0} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1\le i<n}
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i, i] = 0} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1\le i \le n}
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i,i-1] = 0} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1<i\le n}
Rekursion
Für die weiteren Elemente der Matrix gilt, unter der Voraussetzung, dass Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle N[i,0]=0} :
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i,j]=\max \begin{Bmatrix} N[i,j-1] & \\ \max_{i\le k<j-1} (N[i,k-1] + N[k+1,j-1] + 1 )\cdot \sigma(k, j)) & \end{Bmatrix}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1\le i<n, 1<j<n, i<j-1 }
Das Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i,j]} der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} ist nach Beendigung des Algorithmus die maximal mögliche Anzahl von Basenpaaren des Substrings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i..j]} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} . Also ist die maximal mögliche Anzahl von Basenpaaren der gesamten Eingabesequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} in gespeichert.
![{\displaystyle N[1,n-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/825ebe23994a555d6fd88d05ba4c0ed379e454f3)
Die Fallunterscheidung in der Rekursion unterscheidet zwei Fälle. Entweder wird der Substring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i..j-1]} , für den schon die maximal mögliche Anzahl von Basenpaaren schon berechnet wurde, um eine Base erweitert, welche nicht mit einer anderen Base paart. Oder die Base Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[j]} paart mit einer komplementären Base im Substring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i..j-1]} . Im zweiten Fall existieren mögliche Basen, mit denen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[j]} ein Basenpaar bilden könnte. Die Wahl der zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[j]} komplementären Base teilt den Substring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i..j-1]} in zwei Substrings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[i..k-1]} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[k+1..j-1]} , für die die maximale mögliche Anzahl von Basenpaaren rekursiv berechnet wird. Die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma(k,j)} hat den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} , wenn die Base Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle s[k]} komplementär zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s[j]} ist, ansonsten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} .
Die Fallunterscheidung entspricht der kontextfreien Grammatik
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X = X . \mid X ( X ) \mid \epsilon}
wobei ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle .} eine ungepaarte Base bezeichnet und die Klammern Platzhalter für alle möglichen komplementären Basenpaare darstellen. Nach dieser Grammatik können alle Strukturen, über die der Nussinov-Algorithmus optimiert, abgeleitet werden.
Die Sekundärstrukturen, welche die maximalen Basenpaare enthalten, können durch Backtracking von der Zelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[0, n-1]} erzeugt werden. Das heißt, es werden die Pfade durch die Matrix zurückverfolgt, die zu dem optimalen Ergebnis in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N[i, n-1]} führen und in Abhängigkeit dieser Pfade werden die optimalen Sekundärstrukturen erzeugt.
Effizienz
Der Algorithmus verwendet eine Matrix mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{1}{2}n(n+1)+n-1} Einträgen, für jeden Eintrag wird über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n)} Elemente optimiert. Der Speicherbedarf liegt also in der Komplexitätsklasse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n^2)} und die Laufzeit in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n^3)} .
Abgrenzung
Die obige Spezifikation der Matrix-Rekurrenzen entspricht der Darstellung in Nussinov, 1978. Teilweise bezeichnet neuere Literatur eine Abwandlung dieser Rekurrenzen als Nussinov-Algorithmus (z. B. Durbin, 2006). In Durbin, 2006 besteht die Rekursion aus einer Unterscheidung von 4 Fällen. Diese Variation ändert nicht die Werte der berechneten Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} , allerdings repräsentieren dann mehrere unterschiedliche Pfade beim Backtracking eine Sekundärstruktur, da die geänderte Fallunterscheidung semantisch mehrdeutig ist.
Biologische Relevanz
Die Sekundärstruktur, welche die maximale Anzahl von Basenpaaren enthält ist nicht unbedingt die Struktur, die in der Natur (in einer Zelle) auftritt. Ebenso treten in natürlichen RNA-Faltmustern sehr wohl Pseudoknoten auf, die vom Nussinov-Algorithmus von vornherein nicht beachtet werden. In der Praxis wird daher die Sekundärstruktur anders, beispielsweise mit dem Zuker-Algorithmus mit thermodynamischem Modell, vorhergesagt, was zu biologisch sinnvolleren Ergebnissen führt.
Trotzdem ist der Nussinov-Algorithmus von theoretischem Interesse in Forschung und Lehre. Beispielsweise wird in[1] der Algorithmus verwendet, um die Waterman-Byers-Backtracking-Methode zum Backtracking von suboptimalen Strukturen exemplarisch an einer übersichtlichen Matrix-Rekursion zu beschreiben. Die Beschäftigung mit dem Algorithmus ist lehrreich, da er wie andere RNA-Strukturvorhersage-Algorithmen die Methode der dynamischen Programmierung verwendet, aber mit einer Matrix-Rekursion noch relativ einfach verständlich ist.
Literatur
- Ruth Nussinov, George Pieczenik, Jerrold R. Griggs, Daniel J. Kleitman: Algorithms for Loop Matchings. In: SIAM Journal on Applied Mathematics. Band 35, Nr. 1, Juli 1978, S. 68–82.
- Durbin et al.: Biological sequence analysis. Cambridge, 2006, ISBN 0-521-62971-3, S. 269–272.
Einzelnachweise
- ↑ Stefan Wuchty, Walter Fontana, Ivo L. Hofacker, Peter Schuster: Complete Suboptimal Folding of RNA and the Stability of Secondary Structures. In: Biopolymers. Band 49, 1999, S. 145–165 (santafe.edu [PDF; 317 kB]).
