Nussinov-Algorithmus

Algorithmus zur Berechnung der Anzahl von Basenpaaren einer RNA-Sequenz

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.

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.

Algorithmus

Bearbeiten

Der Algorithmus modelliert eine RNA-Sequenz   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   der einzelnen Basen als eine Zeichenkette mit der Länge  . Dabei bezeichnet   das Zeichen an der Stelle   und   die Teil-Sequenz der Zeichen von der Stelle   bis zur Stelle  . Damit ist   gleichbedeutend mit   und   ist  . Weiters sei   eine leere Zeichenkette der Länge 0.

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.

Die Funktion   ergibt 1, wenn   und   komplementäre Basen sind, sonst 0.

Pseudoknoten sind im Modell nicht erlaubt, d. h., für zwei Basenpaare   und   gilt   oder  

Zerlegung in kleinere Teil-Probleme

Bearbeiten

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:

  1. Falls kein Basenpaar gebildet wird, so muss   sein und das Problem ist gelöst.
  2. Falls ein Basenpaar gebildet wird, so kann dieses Basenpaar zwischen   und einer der Basen aus der Teil-Sequenz   gebildet werden. Angenommen, das Basenpaar bildet sich zwischen   und   mit   so teilt sich die Sequenz in die weiteren Teile   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   und   gebildete Basenpaar ergibt einen möglichen Kandidaten-Wert für die Maximale Summe. Der Wert für   soll maximal werden, also muss für jedes erlaubte   die Kandidaten berechnet werden. Der höchste so erreichbare Wert garantiert, dass auch   maximal wird. Somit ist
 

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

Bearbeiten

Die Teil-Sequenzen   der Länge 2,   der Länge 1 und   der Länge 0 enthalten maximal 0 Basenpaare:

  für  
  für  
  für  

Rekursion

Bearbeiten

Für die weiteren Elemente der Matrix gilt, unter der Voraussetzung, dass  :

  mit  

Das Element   der Matrix   ist nach Beendigung des Algorithmus die maximal mögliche Anzahl von Basenpaaren des Substrings   von  . Also ist die maximal mögliche Anzahl von Basenpaaren der gesamten Eingabesequenz   in   gespeichert.

Die Fallunterscheidung in der Rekursion unterscheidet zwei Fälle. Entweder wird der Substring  , 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   paart mit einer komplementären Base im Substring  . Im zweiten Fall existieren   mögliche Basen, mit denen   ein Basenpaar bilden könnte. Die Wahl der zu   komplementären Base teilt den Substring   in zwei Substrings   und  , für die die maximale mögliche Anzahl von Basenpaaren rekursiv berechnet wird. Die Funktion   hat den Wert  , wenn die Base   komplementär zu   ist, ansonsten  .

Die Fallunterscheidung entspricht der kontextfreien Grammatik

 

wobei ein   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   erzeugt werden. Das heißt, es werden die Pfade durch die Matrix zurückverfolgt, die zu dem optimalen Ergebnis in   führen und in Abhängigkeit dieser Pfade werden die optimalen Sekundärstrukturen erzeugt.

Effizienz

Bearbeiten

Der Algorithmus verwendet eine Matrix mit   Einträgen, für jeden Eintrag wird über   Elemente optimiert. Der Speicherbedarf liegt also in der Komplexitätsklasse   und die Laufzeit in  .

Abgrenzung

Bearbeiten

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  , allerdings repräsentieren dann mehrere unterschiedliche Pfade beim Backtracking eine Sekundärstruktur, da die geänderte Fallunterscheidung semantisch mehrdeutig ist.

Biologische Relevanz

Bearbeiten

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

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

Bearbeiten
  1. 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]).