Zuker-Algorithmus

Der Zuker-Algorithmus berechnet die optimale Sekundärstruktur einer RNA-Sequenz mit der minimalen freien Energie unter einem gegebenen thermodynamischen Modell. Es ist also ein Algorithmus zur RNA-Strukturvorhersage. Der Algorithmus verwendet die Methode der Dynamischen Programmierung und wurde 1981 veröffentlicht. Das RNA-Strukturvorhersageprogramm mfold implementiert eine veränderte Version dieses Algorithmus.

Idee

Kleeblattartige Sekundärstruktur der Konsensus-Sequenz eines CIS-Elements der Enterovirus-Familie.

Eine gegebene RNA-Sequenz kann aufgrund vieler möglicher Kombinationen von Basenpaarungen in exponentiell viele verschiedene Sekundärstrukturen gefaltet werden. Bei der Strukturvorhersage muss über dem Suchraum nach einem bestimmten Kriterium optimiert werden. Beispielsweise kann die Struktur mit den meisten Basenpaarungen ausgewählt werden. Diese Struktur kann allerdings biologisch bzw. biochemisch unrealistisch sein, da sie z. B. eine Hairpinloop mit nur einer ungepaarten Base enthält oder eine energetisch sehr instabile Struktur darstellt.

Ein biologisch sinnvolleres Kriterium ist die Betrachtung der freien Energie einer Sekundärstruktur. Ist die freie Energie einer Struktur kleiner als die freie Energie einer anderen Struktur, dann ist die erste Struktur stabiler als die zweite. Unter Laborbedingungen kann die freie Energie von vielfältigen Teilstrukturen einer RNA-Sekundärstruktur gemessen werden. Ein Beispiel für so eine Datensammlung ist ^[1]. Aus diesen Daten kann dann die freie Energie einer gegebenen RNA-Sekundärstruktur einer gegebenen RNA-Sequenz approximiert werden.

Der Algorithmus berechnet nun bei einer gegebenen RNA-Sequenz die Struktur mit der minimalen freien Energie. Die unter diesem Modell optimalen Sekundärstrukturen werden von Experten (Biologen, Biochemikern) als biologisch realistischer beurteilt.

Algorithmus

Die RNA-Sequenz wird mit $ s $ bezeichnet, wobei $ n=|s| $. Die minimale freie Energie einer optimalen Sekundärstruktur wird rekursiv für alle Teilsequenzen von $ s $ berechnet. Die 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/“:): W speichert 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/“:): W[i,j] die minimale freie Energie (mfe) für die Teilsequenz 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. Die 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/“:): V speichert 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/“:): V[i,j] die mfe der Struktur der Teilsequenz 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] , wobei 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] und $ s[j] $ ein Basenpaar sind.

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/“:): W[i,j] = 0, j-i = 4

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/“:): V[i,j] = 8.4 kcal/mol, j-i = 4

Kurze RNA-Moleküle formen keine stabile Sekundärstruktur.

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/“:): W[i,j] = \min\begin{Bmatrix} W[i+1,j] \\ W[i,j-1] \\ \min_{i<k<j-1} \{ W[i,k] + W[k+1,j] \} \\ V[i,j] \end{Bmatrix}, i<j, j-i>4, 0<i<n, 0<j<n

Die Fallunterscheidung berücksichtigt vier Fälle. Im ersten bzw. zweiten Fall setzt sich die optimale Struktur 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/“:): s[i..j] aus dem optimalen Struktur der Teilsequenz 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+1,j] bzw. 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] und einer ungepaarten Base links bzw. rechts davon zusammen. In beiden Fällen ändert sich nichts an der mfe.

Im dritten Fall wird die optimale Struktur 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/“:): s[i..j] gebildet, indem die optimalen Strukturen der geteilten Sequenz konkateniert werden. Die mfe ist die Summe der mfe der Teilstrukturen der Teilsequenzen $ s[i,k] $ bzw. 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] .

Der 4. Fall ermittelt die mfe für eine Teilsequenz 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/“:): s[i..j] , falls die Basen 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] 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[j] ein Basenpaar darstellen.

Falls 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] nicht 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[j] ein Basenpaar bilden kann, dann wird

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/“:): V[i,j] = \inf

gesetzt.

Ansonsten wird $ V[i,j] $ wie folgt berechnet:

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/“:): V[i,j] = \min\begin{Bmatrix} fh(i,j) \\ \min_{i<a<b<j} \{ fl(i,j,a,b) + V(a,b) \} \\ \min_{i+1<k<j-2} \{ W(i+1,k) + W(k+1, j-1) \} \end{Bmatrix}, i<j, j-i>4, 0<i<n, 0<j<n

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/“:): fh gibt die freie Energie für einen Hairpin-Loop der Teilsequenz 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] zurück. Beispielsweise können die Werte für verschiedene Loop-Größen und Basenpaare experimentell unter einheitlichen Bedingungen ermittelt werden und sind in einer Hilfstabelle gespeichert. 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/“:): fl ist ein Stellvertreter und liefert die freie Energie für eine Internal-Loop, eine Bulge-Loop oder eine Stacking-Region, an der die Teilsequenzen 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..a] 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[b..j] beteiligt sind. Die mfe ist in diesem Fall die Summe dieses Konstruktes und der mfe für die Teilsequenz $ s[a,b] $, welche von einem Basenpaar eingeschlossen sein muss. Der vierte Fall modelliert eine Verzweigung der rekursiv konstruierten Struktur.

Backtracing: 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/“:): W[0,n-1] ist nach der Berechnung der Matrix-Rekurrenzen die mfe für die gesamte RNA-Sequenz unter einer optimalen Sekundärstruktur gespeichert. Um eine optimale Sekundärstruktur zu ermitteln, welche die mfe hat, muss Optimierung via Backtracking zurückverfolgt werden.

Komplexität

Die beiden Tabellen 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/“:): W 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/“:): V sind quadratisch, 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 jede Zelle muss – bei trivialer Implementierung – ü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^2) Möglichkeiten optimiert werden, denn interior loops benötigen 2 Variable. Durch ein geschicktes Preprocessing, also ein Vorab-Berechnen der Werte für interior loops kann man aber auch diesen Energiebeitrag in linearer Zeit bestimmen. Alternativ kann man die Größe eines loops mit einer Konstante beschränken. Damit liegt die Laufzeit des Algorithmus in $ O(n^{3}) $.

Fallunterscheidung

Die Fallunterscheidung in der Rekursion der 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/“:): W -Rekurrenz des Algorithmus lässt sich auch kompakter formulieren, wenn die Sekundärstrukuren als Vienna-Strings (Dot-Bracket-Strings) abgebildet werden. Wenn ein Punkt eine ungepaarte Base und eine Klammer eine gepaarte Base bezeichnet, dann entspricht die Fallunterscheidung in der Rekursion 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/“:): W folgender Fallunterscheidung

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/“:): u = v. | .v | ( v ) | vw ,

wobei 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/“:): u die Gesamtsekundärstruktur eines Teilstrings bezeichnet 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/“:): v bzw. 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/“:): w Teilstrukturen von $ u $ bezeichnen.

Diese Beschreibung ist äquivalent zu folgenden grafischen Darstellung:

• Junpaired.jpg

  j ungepaart

• Iunpaired.jpg

  i ungepaart

• Ijpair.jpg

  i und j gepaart

• 

  Verzweigung

Backtracing

Beim Backtracing können aufgrund der Fallunterscheidung des Zuker-Algorithmus mehrere unterschiedliche Backtracing-Pfade die gleiche Sekundärstruktur repräsentieren. Die Fallunterscheidung ist semantisch mehrdeutig. Beispielsweise eine Rekursion in $ W $ von Fall 1 nach Fall 2 nach Fall 1 erzeugt die gleiche Struktur wie die Rekursion von Fall 1 nach Fall 1 nach Fall 2. Für ein weiteres Beispiel siehe ^[2].

Diese Mehrdeutigkeit ist nicht problematisch bei der Ausgabe einer optimalen Sekundärstruktur. Wenn allerdings alle co-optimalen Sekundärstrukturen ausgegeben oder gezählt oder alle suboptimalen Strukturen bis zu einer gewissen Schranke ausgegeben oder gezählt werden sollen, dann ist das Backtracing zumindest nur noch schwer fehlerfrei, effizient und vollständig implementiertbar. Bei einer Standard-Backtracing-Implementation werden die redundanten Strukturen in exponentieller Anzahl ausgegeben bzw. gezählt.

Abgrenzung

Der Algorithmus verwendet eine weitere Tabelle im Vergleich zu dem Nussinov-Algorithmus, um eine Folge von gepaarten Basen (also eine Stacking-Region), unterschiedlich bewerten zu können. Eine ähnliches Muster verwendet auch der Gotoh-Algorithmus zur Berechnung des paarweisen Sequenzalignment bei affinen Gapkosten.

Der Nussinov-Algorithmus von 1978 berechnet die Sekundärstruktur einer RNA-Eingabesequenz, welche die maximale Anzahl von Basenpaaren hat. Da diese Strukturen nicht unbedingt biologisch sinnvoll sind, ist der Nussinov-Algorithmus nicht praxisrelevant. In der Praxis werden unter anderem RNA-Sekundärstrukturvorhersage Algorithmen verwendet, die die Struktur mit der minimalen freien Energie berechnen bzw. die Strukturen mit den kleinsten freien Energien bis zu einer gewissen Schwelle bestimmen. Die Verwendung des Zuker-Algorithmus in der mfold-Implementation ist immer noch verbreitet, obwohl inzwischen auch Algorithmen zur Sekundärstrukturvorhersage existieren, die eine detaillierte Fallunterscheidung vornehmen und deren Fallunterscheidung nicht mehrdeutig ist. Ein Beispiel für so einen verbesserten mfe-Algorithmus ist der Wuchty98-Algorithmus.

Literatur

• Michael Zuker and Patrick Stiegler: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. In: Nucleic Acids Research. 9, Nr. 1, 1981, S. 133-148.
• Durbin et al.: Biological sequence analysis. Cambridge, 2006, ISBN 0-521-62971-3, S. 274-276.
• Jens Reeder: Algorithms for RNA secondary structure analysis : prediction of pseudoknots and the consensus shapes approach. 2007, S. 13-15 (http://bieson.ub.uni-bielefeld.de/volltexte/2008/1276/).

Quellen