Needleman-Wunsch-Algorithmus

Optimierungsalgorithmus aus der Bioinformatik

Der Needleman-Wunsch-Algorithmus ist ein Optimierungsalgorithmus aus der Bioinformatik. Dort wird er zum Vergleich zweier Nukleotid- bzw. Aminosäuresequenzen eingesetzt. Er berechnet anhand eines Modells den optimalen globalen Similarity-Score bzw. mit Hilfe von Backtracking ein oder mehrere optimale globale Alignments zwischen zwei Sequenzen. Der Similarity-Score ist ein Maß für die Ähnlichkeit zweier Sequenzen; je höher der Score, umso ähnlicher sind die Sequenzen unter dem angewendeten Scoring-Modell. Der Algorithmus optimiert den Score des Alignments. Dabei ist ein Alignment eine Folge von Editierschritten, um die erste Sequenz in die zweite zu überführen. Für zwei nichttriviale Sequenzen gibt es viele Alignments – ein optimales Alignment hat einen maximalen Similarity-Score. Der Algorithmus verwendet die Methode der dynamischen Programmierung und erlaubt beliebige Scoring-Modelle (d. h. die Verwendung allgemeiner Gap-Kosten) für die Editierschritte.

Das Verfahren

Bearbeiten

Der Needleman-Wunsch-DP-Algorithmus berechnet in einer Matrix für alle Paare von möglichen Präfixen der Sequenzen a und b den optimalen globalen Similarity-Alignment-Score. Das Element   der Matrix enthält den optimalen Score für das optimale globale Alignment der Teilsequenz   von a und   von b. Die Schreibweise   entspricht dem i-ten Praefix   von a. Wenn m die Sequenzlänge von a bzw. n die Sequenzlänge von b bezeichnet, dann enthält die Score-Matrix M   Zeilen und   Spalten. Der Alignment-Score der vollständigen Sequenzen ist nach der Ausführung des Algorithmus in   enthalten.

Die Score-Matrix wird rekursiv berechnet. Für das Element (i,j) der Matrix M wird über drei Fälle maximiert. Die Erweiterung des bisherigen Alignments der Sequenzen   und   um ein Match bzw. Mis-Match, entspricht der Addition des zuvor berechneten Scores aus   und der Kosten für die Ersetzung von   durch  . Die Erweiterung eines schon berechneten Alignments um eine abschließende Löschung, entspricht der Addition der allgemeinen Gap-Kosten der Länge der Löschung zu dem Score des optimalen Alignments der Sequenzen   und  , wobei   die Länge der Löschung bezeichnet. Analog zur Löschung entspricht die Erweiterung eines optimalen Alignments der Sequenzen   und   um eine abschließende Einfügung der Addition des Scores dieses Alignments und der Gap-Kosten für die Länge   der Einfügung. Der maximale Wert dieser drei Alternativen wird im Element   gespeichert.

Die Gap-Kostenfunktion kann allgemein sein. D. h. es wird nicht vorausgesetzt, dass einheitliche Kosten oder Affine-Gap-Kosten verwendet werden.

Die bisher informell beschriebenen Matrix-Rekursion sind im nächsten Abschnitt formal aufgeschrieben. Um die Abhängigkeiten der Rekursion zu berücksichtigen, muss die Score-Matrix zeilen- oder spaltenweise berechnet werden.

Das Alignment kann durch Backtracking ausgegeben werden. Als ein mögliches Backtracking-Verfahren kann man während der Berechnung der Score-Matrix in einer Hilfs-Matrix für jedes Element   speichern, ob der maximale Wert durch eine Einfügung, Löschung oder durch ein Match berechnet wurde. Vom Element   der Matrix   kann nach der vollständigen Berechnung der Matrix der Pfad zur Berechnung des maximalen zurückverfolgt und dabei das optimale Alignment konstruiert werden. Für zwei Sequenzen existieren in einer Matrix ein oder mehrere optimale Pfade in einer Score-Matrix die zu dem optimalen Score führen, ebenso wie für zwei Sequenzen mehrere Alignments existieren können, welche den optimalen Score besitzen.

Matrix-Rekursion

Bearbeiten

Spezifikation des Algorithmus durch Matrix-Rekursionen:

 

 

 

 

  •   : Zeichenketten über einem Alphabet  
  •  
  •  
  •   : maximale Similarity-Score zwischen einem Präfix von  , welches in   endet und einem Präfix von  , welches in   endet
  •   : Similarity-Score-Funktion
  •   : allgemeine Gap-Kostenfunktion

Beispiel

Bearbeiten

Anhand eines kleinen Beispiels werden hier die Schritte des Algorithmus vorgestellt.

Als Bewertungsfunktion wird die folgende Funktion benutzt:

 

a = ACGTC und b = AGTC

Zum besseren Verständnis kann man sich vorstellen, dass die Zeilen mit den Buchstaben aus Sequenz a gelabelt sind und die Spalten mit den Buchstaben aus Sequenz b. Mathematisch gesehen ergibt dies innerhalb der Matrix keinen Sinn, deshalb ist dies hier nur zur Anschauung.

 

0. Schritt: Initialisierung

Die Einträge der Matrix   für die erste Zeile und die erste Spalte wird wie oben beschrieben gefüllt. Die Bewertung für den Eintrag   wird berechnet aus der darüberliegenden Bewertung   und dem Score an der Stelle  . Also   die anderen Werte werden nun analog berechnet.

 

1. Schritt: Berechnung von  :

 

→ Das Maximum entsteht aus dem ersten Fall, d. h. A wird mit A aligniert.

 

→ Erhöhung von j um 1, i bleibt gleich

2. Schritt: Berechnung von  :

 

→ Das Maximum entsteht aus dem dritten Fall, da hier das Maximum der Berechnung, nämlich 0 entsteht, d. h. ein Gap(-) würde mit C aligniert.

 

 

Die gefüllte Matrix sieht nach vollständiger Ausführung der o.a. Schritte folgendermaßen aus:

 

Die Bewertung dieses Alignments ist 3.

Das dazugehörige Alignment sieht so aus:

 

Berechnet wird es durch ein Traceback.

Wahl der Bewertungsfunktion

Bearbeiten

Die Wahl der Bewertungsfunktion hat einen großen Einfluss auf die Ergebnisse, die man durch den Needleman-Wunsch-Algorithmus erhält. Eine einfache Bewertungsfunktion wie oben gewählt spiegelt keinesfalls den biologischen Hintergrund eines Alignments wider und ist deshalb für praktische Zwecke eher ungeeignet. Die im Moment gebräuchlichsten Bewertungsfunktionen lesen die Bewertung aus einer sogenannten Scoring Matrix aus. Für Proteine kann man die PAM- oder Blosum-Matrizen benutzen. Diese Matrizen mit der Größe 20×20 (bzw. 24×24, wenn noch einige Sonderfälle beachtet werden) enthalten Bewertungen (sogenannte log-odds) dafür, dass eine Aminosäure durch eine andere substituiert wird. Die log-odds basieren auf Wahrscheinlichkeiten. Berechnet werden diese Scoring-Matrizen ebenfalls aus Sequenzalignments.

Die oben verwendete Bewertungsfunktion wird benutzt, um die Ähnlichkeit zweier Sequenzen zu bestimmen. Um nun die Distanz bestimmen zu können, kann man einfach die Bewertungsfunktion ändern, d. h. bei Ungleichheit kann man einen positiven Wert zurückgeben, welcher als Strafe interpretiert werden kann und bei Gleichheit 0 oder einen negativen Wert. Es muss allerdings beachtet werden, dass in der Rekursion bei einer distanzbasierten Bewertungsfunktion nicht das Maximum, sondern das Minimum ermittelt werden muss.

Ein Beispiel für eine distanzbasierte Bewertungsfunktion:

 

Komplexität

Bearbeiten

Die Laufzeit des Needleman-Wunsch Algorithmus liegt in   . Es müssen   Elemente der Matrix berechnet und für jedes dieser über drei maximiert werden[1]. Dies lässt sich einfach aus den Matrix-Rekursionen ableiten. Der Speicherbedarf liegt bei Konstruktion der gesamten Tabelle in   .

Abgrenzung

Bearbeiten

Im Needleman-Wunsch Paper von 1970 sind keine Matrix-Rekursionen enthalten, der Algorithmus wird dort informell beschrieben; die hier dargestellten Matrix-Rekursionen ergeben sich aus dieser Beschreibung.

In einem Paper von Waterman, Smith und Beyer von 1976[2] wird der Needleman-Wunsch-Algorithmus explizit in Matrix-Rekursionen spezifiziert. Deswegen bezeichnen auch manche Autoren den Needleman-Wunsch-Algorithmus als Waterman-Smith-Beyer-Algorithmus.[3]

In mancher Literatur wird der Standard   DP-Algorithmus zur Berechnung des globalen Alignments unter einheitlichen Gap-Kosten fälschlicherweise als Needleman-Wunsch-Algorithmus bezeichnet.[4] Dies ist allerdings eine Spezialisierung des Needleman-Wunsch Algorithmus, da bei der Verwendung einheitlicher Gap-Kosten für die Edit-Operationen nur die drei benachbarten Zellen beachtet werden müssen.

Aufgrund der kubischen Laufzeit wird der Needleman-Wunsch-Algorithmus in der Praxis nicht eingesetzt. Bei Beschränkung auf einheitliche Kosten kann mit oben beschriebener Optimierung das optimale Alignment in   berechnet werden. Mit dem Gotoh-Algorithmus kann das optimale Alignment bei affinen Gap-Kosten in quadratischer Laufzeit berechnet werden. Der Hirschberg-Algorithmus berechnet ein globales Alignment bei einheitlichen bzw. affinen Gap-Kosten auf linearem Speicherplatz   in Zeit   und der Smith-Waterman-Algorithmus berechnet das optimale lokale Alignment zweier Sequenzen.

Speicher-Abschätzung

Bearbeiten

Wegen des quadratischen Speicherbedarfs ist der Algorithmus für das Alignieren längerer Sequenzen eher ungeeignet. Wenn z. B. in der Matrix Integer-Werte, welche jeweils 4 Byte groß sind, gespeichert werden, dann benötigt die Berechnung des Alignment-Scores einer Sequenz von 10.000 Zeichen eine Matrix mit   Einträgen. Also werden von der Matrix   belegt. Die Alignierung ganzer Genome lässt sich so nicht effizient durchführen. Beispielsweise hat ein mittleres Bakteriengenom ca. 1–4 Millionen Basenpaare und das menschliche Genom ca. 3 Milliarden Basenpaare.

Abgesehen davon hat ein globales Alignment ganzer Genome nicht unbedingt einen hohen biologischen Erkenntnisgewinn.

Varianten

Bearbeiten

Einheitliche Gap-Kosten

Bearbeiten

Bei Verwendung von einheitlichen Gap-Kosten ist eine Spezialisierung der Matrix-Rekursionen des Needleman-Wunsch-Algorithmus möglich, wodurch sich die Laufzeit von   auf   reduziert. Sellers hat diese Rekursionen in einem Paper von 1974 explizit spezifiziert.[5]

Eine einheitliche Gap-Kosten-Funktion   ist definiert durch  , d. h. jede Stelle eines Gaps kostet gleich viel. Unter Verwendung von einheitlichen Gap-Kosten ist bei der Betrachtung eines optimalen Alignment der Präfixe   und  , das in einem Insertions-Gap der Länge   mit   endet, direkt einsehbar, dass auch das optimale Alignment der Präfixe   und   in einem Insertions-Gap endet. Daher reicht es aus, zur Berechnung der Kosten eines optimalen Insertions-Gap (beliebiger Länge) in  ,   zu rechnen. Die Berechnung der Deletions-Gap-Kosten erfolgt analog.

Daraus ergeben sich folgende spezialisierte Rekursionen:

 

 

 

 

Free-Shift Alignment

Bearbeiten

Die Berechnung des optimalen Free-Shift Alignment (oder End-Gap Free Alignment) ist eine Variante des Needleman-Wunsch-Algorithmus, bei der eine Folge von Insertionen bzw. Deletionen am Anfang bzw. Ende des Alignment in der Score-Berechnung nicht berücksichtigt werden. Dazu wird der Algorithmus zur Berechnung des globalen Alignment so abgeändert, dass die erste Zeile bzw. erste Spalte mit   initialisiert werden. Beim Backtracking wird der maximale Wert in der letzten Spalte bzw. Zeile gesucht und als Ausgangspunkt benutzt.

Einzelnachweise

Bearbeiten
  1. R. Wagner, M. Fischer: The string-to-string correction problem. In: J. ACM. 21. Jahrgang, 1974, S. 172, doi:10.1145/321796.321811.
  2. Waterman, Smith, Beyer: Some Biological Sequence Metrics. In: Advances in Mathematics. Band 20, 1976, S. 367–387, doi:10.1016/0001-8708(76)90202-4 (Theorem 3).
  3. P. Clote, R. Backofen: Computational Molecular Biology. Wiley, 2000, ISBN 0-471-87251-2.
  4. D. Gusfield: Algorithms on Strings, Trees and Sequences. 1997, ISBN 0-521-58519-8, 11.7.3, S. 234.
  5. Peter H. Sellers: On the Theory and Computation of Evolutionary Distances. In: SIAM Journal on Applied Mathematics. Band 26, Nr. 4, Juni 1974, S. 787–793, JSTOR:2099985.

Literatur

Bearbeiten
Bearbeiten
Commons: Needleman-Wunsch-Algorithmus – Sammlung von Bildern, Videos und Audiodateien