NussinovAlgorithmen

Der Nussinov-Algorithmus ist ein dynamisch programmierendes Verfahren zur Vorhersage der RNA-Sekundärstruktur. Er wurde von Ruth Nussinov und Mitautorinnen/Mitautoren eingeführt und dient der berechneten Bestimmung einer pseudoknotfreien Struktur durch Maximierung der Anzahl von Basenpaaren. Der Ansatz liefert eine einfache, theoretisch klare Grundlage für das Verständnis von RNA-Faltung, ist jedoch eine grobe Näherung im Vergleich zu thermodynamischen Modellen.

Der Kern des Algorithmus besteht in einer dynamischen Programmierung über Teilsequenzen. Sei S eine Sequenz der Länge n, und DP[i][j] die maximale Anzahl von Basenpaaren in der Teilsequenz von i bis j. Dann gilt DP[i][j] = max von mehreren Optionen: DP[i+1][j], DP[i][j-1], DP[i+1][j-1] + w(i,j) sowie der Bifurkationsausdruck max_{k}(DP[i][k] + DP[k+1][j]). Dabei ist w(i,j) gleich 1, wenn Position i und Position j ein gültiges Basenpaar bilden (typischerweise A-U, G-C, G-U), sonst 0. Die Bifurkation berücksichtigt, dass eine Teilsequenz weiter in zwei Nichtüberlappende Teilstrukturen zerlegt werden kann. Nicht alle Paare müssen gebildet werden; das Ziel ist die maximale Gesamtzahl der Paare.

Komplexität und Rekonstruktion: Die Berechnung benötigt typischerweise O(n^3)-Zeit und O(n^2)-Speicher. Durch Backtracking lässt sich eine entsprechende sekundäre Struktur aus der DP-Tabelle rekonstruieren. Es entsteht eine bevorzugte, plausible, aber oft stark vereinfachte Struktur.

Einschränkungen und Relevanz: Der Algorithmus behandelt keine Pseudoknots und beruht auf der Maximierung der Basenpaare, nicht auf einer energiebasierten Optimierung. Er dient meist als Baseline oder Lehrbeispiel in der RNA-Bioinformatik; spätere Modelle wie das Zuker- oder energetische Ansätze integrieren umfassendere Thermodynamik und Pseudoknots.