Nussinov-Algorithmus

Eine von dem Nussinov-Algorithmus berechnete optimale Sekundärstruktur einer RNA-Sequenz aus einem Viren-Genom. Sie hat 18 Basenpaare und es existieren 41 weitere co-optimale Sekundärstrukturen dieser Eingabesequenz mit 18 Basenpaaren.

Der Nussinov-Algorithmus berechnet die maximal mögliche Anzahl von Basenpaaren einer gegebenen Nukleinsäure-Sequenz. In einer zweiten Phase kann die Sekundärstruktur mit den meisten Basenpaaren bzw. können die Sekundärstrukturen mit den meisten Basenpaaren konstruiert werden. Der Algorithmus verwendet die Methode der dynamischen Programmierung.

Algorithmus

$$ n $$ ist die Länge der Eingabesequenz $$ s $$ . N bezeichnet eine $n\times n$ Matrix und die Funktion $\sigma (i,j)$ liefert 1, wenn $$ s[i] $$ komplementär zu $$ s[j] $$ ist, sonst 0 zurück.

Es sind keine überlappenden Basenpaare erlaubt, d.h. für die Basenpaare mit den Indizes $$ (a,b) $$ mit $$ a<b $$ 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/“:): (c, d) 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/“:): c<d darf nicht 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/“:): a<c<b<d oder 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/“:): c<a<d<b gelten.

Substrings werden 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/“:): s[i..j] 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/“:): s[i..i] ist der Substring der Länge 1, der dem Zeichen 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/“:): s[i] entspricht und $$ s[i..i-1] $$ bezeichnet den Substring der Länge 0, also den leeren String.

Initialisierung

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/“:): N[i,i] = 0, 0\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/“:): N[i,i-1] = 0, 0<i<n

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/“:): s[i,i] der Länge 1 und der leere 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/“:): s[i,i-1] der Länge 0 enthalten maximal 0 Basenpaare.

Rekursion

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/“:): N[i,j]=\max \begin{Bmatrix} N[i,j-1] & \\ \max_{i\le k<j-1} (N[i,k-1] + 1 + N[k+1,j-1])\cdot \sigma(k, j) & \end{Bmatrix}, 0\le i<n, 0<j<n, i<j

In 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/“:): N[i,j] der Matrix N steht 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/“:): s[i..j] von $$ 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/“:): s 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/“:): N[0,n-1] gespeichert.

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/“:): 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/“:): 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/“:): s[i..j-1] . Im zweiten Fall existieren 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/“:): k 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/“:): 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/“:): s[j] komplementären Base teilt den Substring $$ 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/“:): 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/“:): 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/“:): \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/“:): 1 , wenn 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/“:): 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/“:): 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/“:): 0 .

Die Fallunterscheidung entspricht der kontextfreien Grammatik

$X=X.|X(X)|\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/“:): . 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ärstrukuren, 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/“:): N[0, n-1] erzeugt werden. D.h. 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/“:): 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/“:): n*(n+1)/2+n-1 Einträgen. Also liegt der Speicherbedarf 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/“:): O(n^2) . 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/“:): O(n) Elemente optimiert und deshalb liegt die Laufzeit in des Algorithmus 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/“:): 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 $$ 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. Deshalb wird in der Praxis der Nussinov-Algorithmus nicht zur Strukturvorhersage von RNA-Sequenzen eingesetzt. In der Praxis wird die Sekundärstruktur beispielsweise unter einem thermodynamischen Modell vorhergesagt (siehe beispielsweise Zuker-Algorithmus), 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-Rekurrenz 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-Rekurrenz noch relativ einfach verständlich ist.

Einzelnachweise

↑ Stefan Wuchty, Walter Fontana, Ivo L. Hofacker, Peter Schuster: Complete Suboptimal Folding of RNA and the Stability of Secondary Structures. In: Biopolymers. 49, 1999, S. 145-165 (PDF, 317 KB).

Literatur

Ruth Nussinov and George Pieczenik and Jerrold R. Griggs and Daniel J. Kleitman: Algorithms for Loop Matchings. In: SIAM Journal on Applied Mathematics. 35, Nr. 1, Juli 1978, S. 68-82.
Durbin et al.: Biological sequence analysis. Cambridge, 2006, ISBN 0-521-62971-3, S. 269-272.

[1] Stefan Wuchty, Walter Fontana, Ivo L. Hofacker, Peter Schuster: Complete Suboptimal Folding of RNA and the Stability of Secondary Structures. In: Biopolymers. 49, 1999, S. 145-165 (PDF, 317 KB).

[1]