Meine Merkliste

Home
Lexikon
Needleman-Wunsch-Algorithmus

Needleman-Wunsch-Algorithmus

Der Needleman-Wunsch Algorithmus berechnet fuer allgemeine Gap-Kosten das globale Alignment bzw. den global optimalen Similarity-Score zweier Sequenzen a und b. Er verwendet die Programmiermethode der dynamischen Programmierung.

Weiteres empfehlenswertes Fachwissen

Wie kann man Pipetten schnell überprüfen?

Wie erhalten Sie Tag für Tag genaue Wägeresultate?

Lassen Sie sich von statischen Aufladungen nicht die Wägegenauigkeit stören.

Das Verfahren

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 $i, j$ der Matrix enthält den optimalen Score für das optimale globale Alignment der Teilsequenz $a [0.. i]$ von a und $b [0.. j]$ von b. Die Schreibweise $a [0.. i]$ entspricht dem i-ten Praefix $a_1, a_2,\dots,a_i$ von a. Wenn m die Sequenzlänge von a bzw. n die Sequenzlänge von b bezeichnet, dann enthält die Score-Matrix M $m + 1$ Zeilen und $n + 1$ Spalten. Der Alignment-Score der vollständigen Sequenzen ist nach der Ausführung des Algorithmus in $M (m, n)$ enthalten.

Die Score-Matrix wird rekurrent berechnet. Für das Element (i,j) der Matrix M wird über drei Fälle maximiert. Die Erweiterung des bisherigen Alignments der Sequenzen $a [0.. i - 1]$ und $b [0.. j - 1]$ um ein Match bzw. Mis-Match, entspricht der Addition des zuvor berechneten Scores aus $M (i - 1, j - 1)$ und der Kosten für die Ersetzung von $a [i]$ zu $b [i]$ . Die Erweiterung eines schon berechneten Aligments 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 $a [0.. i - k]$ und $b [0.. j]$ , wobei $k$ die Länge der Löschung bezeichnet. Analog zur Löschung entspricht die Erweiterung eines optimalen Alignments der Sequenzen $a [0.. i]$ und $b [0.. j - l]$ um eine abschließende Einfügung der Addition des Scores dieses Alignments und der Gap-Kosten für die Länge $l$ der Einfügung. Der maximale Wert dieser drei Alternativen wird im Element $M (i, j)$ 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-Rekurrenzen sind im nächsten Abschnitt formal aufgeschrieben. Um die Abhängigkeiten der Rekurrenz nicht zu verletzen, 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 $(i, j)$ speichern, ob der maximale Wert durch eine Einfügung, Löschung oder durch ein Match berechnet wurde. Vom Element $(n, m)$ der Matrix $M$ 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-Rekurrenzen

Spezifikation des Algorithmus durch Matrix-Rekurrenzen:

$M (0,0) = 0$

$M(i,0) = f(i),\; 1\le i\le m$

$M(0,j) = f(j),\; 1\le j\le n$

$M(i,j) = \max \begin{Bmatrix} M(i-1,j-1) + \ w(a_i,b_j) & \text{Match bzw. Mismatch} \\ \max_{1\le k \le i}\{M(i-k,j) + \ f(k)\} & \text{Deletion} \\ \max_{1\le l \le j}\{M(i,j-l) + \ f(l)\} & \text{Insertion} \end{Bmatrix} ,\; 1\le i\le m, 1\le j\le n$

a, b = Zeichenketten über einem Alphabet $Σ$
m = length(a)
n = length(b)
$M (i, j)$ - ist der maximale Similarity-Score zwischen einem Präfix von a, welches in i endet und einem Präfix von b, welches in j endet
$w(c,d),\; c, d\in\Sigma$ , Similarity-Score-Funktion
f, allgemeine Gap-Kostenfunktion

Beispiel

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

Als Bewertungsfunktion wird die folgende Funktion benutzt:

$w(x,y) = \begin{cases} 1 &, x=y \\ -1 &, \textrm{sonst} \\ \end{cases}$

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 macht dies innerhalb der Matrix keinen Sinn, deshalb ist dies hier nur zur Anschauung.

$D = \begin{pmatrix} &-&A&G&T&C\\ -&0&-1&-2&-3&-4 \\ A&-1&0&0&0&0 \\ C&-2&0&0&0&0 \\ G&-3&0&0&0&0 \\ T&-4&0&0&0&0 \\ C&-5&0&0&0&0 \\ \end{pmatrix}$

0. Schritt: Initialisierung

Die Einträge der Matrix $D (i, j)$ für die erste Zeile und die erste Spalte wird wie oben beschrieben gefüllt. Die Bewertung für den Eintrag $D (1,0)$ wird berechnet aus der darüberliegenden Bewertung $D (i - 1, j) = D (0,0) = 0$ und dem Score an der Stelle $w (a i, b i) = w (a 1, - ) = w (A, - ) = - 1$ . Also $D (1,0) = 0 + ( - 1) = - 1$ die anderen Werte werden nun analog berechnet.

$D = \begin{pmatrix} 0&-1&-2&-3&-4 \\ -1&0&0&0&0 \\ -2&0&0&0&0 \\ -3&0&0&0&0 \\ -4&0&0&0&0 \\ -5&0&0&0&0 \\ \end{pmatrix}$

1. Schritt: Berechnung von $D (1,1)$ : $\begin{cases} D(0,0) + w(A,A) \Rightarrow 0 + 1 \\ D(0,1) + w(A,-) \Rightarrow -1 +(-1) \\ D(1,0) + w(-,A) \Rightarrow -1 +(-1) \\ \end{cases}$

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

$D= \begin{pmatrix} 0&-1&-2&-3&-4 \\ -1&1&0&0&0 \\ -2&0&0&0&0 \\ -3&0&0&0&0 \\ -4&0&0&0&0 \\ -5&0&0&0&0 \\ \end{pmatrix}$

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

2. Schritt: Berechnung von $D (1,2)$ : $\begin{cases} D(0,1) + w(A,C) \Rightarrow -1 +(-1) \\ D(0,2) + w(A,-) \Rightarrow -2 +(-1) \\ D(1,1) + w(-,C) \Rightarrow 1 +(-1) \\ \end{cases}$

→ 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.

$D= \begin{pmatrix} 0&-1&-2&-3&-4 \\ -1&1&0&0&0 \\ -2&0&0&0&0 \\ -3&0&0&0&0 \\ -4&0&0&0&0 \\ -5&0&0&0&0 \\ \end{pmatrix}$

$\vdots$

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

$D= \begin{pmatrix} 0&-1&-2&-3&-4 \\ -1&1&0&-1&-2 \\ -2&0&0&-1&0 \\ -3&-1&1&0&-1 \\ -4&-2&0&2&1 \\ -5&-3&-1&1&3 \\ \end{pmatrix}$

Die Bewertung dieses Alignments ist 3.

Das dazugehörige Alignment sieht so aus:

$\begin{matrix} \textrm{Sequenz} \ a: &A&C&G&T&C \\ \textrm{Sequenz} \ b: &A&-&G&T&C\end{matrix}$

Berechnet wird es durch ein Traceback.

Wahl der Bewertungsfunktion

Die Wahl der Bewertungsfunktion hat einen großen Einfluss auf die Ergebnisse, die man durch den Needleman-Wunsch-Algorithmus erhält. Eine einfach Bewertungsfunktion wie oben gewählt spiegelt keinesfalls den biologischen Hintergrund eines Alignments wieder 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 Bewertungfunktion nicht das Maximum, sondern das Minimum ermittelt werden muss.

Ein Beispiel für eine distanzbasierte Bewertungsfunktion:

$w(x,y)= \begin{cases} 0 &, x \ = \ y \\ 1 &, x \ \not= \ y \\ \end{cases}$

Komplexität

Die Laufzeit des Needleman-Wunsch Algorithmus liegt in $O (m a x (n, m) 3)$ . Es müssen $m\cdot n$ Elemente der Matrix berechnet werden, und für jedes Element muss über $O (n) + O (m)$ Elemente maximiert werden. Dies läßt sich einfach aus den Matrix-Rekurrenzen ableiten. Der Speicherbedarf liegt in $O (n m)$ .

Abgrenzung

In dem Needleman-Wunsch Paper von 1970 sind keine Matrix-Rekurrenzen enthalten, der Algorithmus wird dort informell beschrieben; die Matrix-Rekurrenzen ergeben sich aus dieser Beschreibung.

In mancher Literatur wird der Standard $O (n 2)$ DP-Algorithmus zur Berechnung des globalen Alignments unter einheitlichen Kosten fälschlicherweise als Needleman-Wunsch-Algorithmus bezeichnet (Gusfield 1999, ein Beispiel sind alte Versionen dieses Artikels). Dies ist allerdings eine Spezialisierung des Needleman-Wunsch Algorithmus, da bei der Verwendung einheitlicher 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 $O (n 2)$ 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 $O (m + n)$ in Zeit $Θ(m n)$ und der Smith-Waterman-Algorithmus berechnet das optimale lokale Alignment zweier Sequenzen.

Speicher-Abschätzung

Der Algorithmus ist daher für lange Alignments eher ungeeignet. Wenn man davon ausgeht, dass man Integerwerte speichert und diese in Java 4 Byte Speicher belegen, kommt man bei einem Alignment von $10.000 * 10.000$ Buchstaben schon auf $100.000.000 * 4$ Byte $\approx$ 381 MegaByte. Die Alignierung ganzer Genome lässt sich so allerdings noch nicht optimal durchführen. (Ein mittleres Bakteriengenom hat ca. 1 - 4 Millionen Basenpaare. Das menschliche Genom z.B. hat ca. 3 Milliarden Basenpaare).

Abgesehen davon ist die Array-Größe in Java auf 2 GB beschränkt und ein globales Alignment ganzer Genome hat nicht unbedingt einen hohen biologischen Erkenntnisgewinn.

Literatur

Saul B. Needleman, Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48:443-453, 1970
D. Gusfield. Algorithms on Strings, Trees and Sequences. 11.7.3:234, 1999, ISBN 0-521-58519-8

Kategorie: Bioinformatik

Dieser Artikel basiert auf dem Artikel Needleman-Wunsch-Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.