Textsuche

Problem

Gegeben sind zwei Protein­sequenzen, als einfaches Beispiel etwa die Sequenzen MAEHTE und AEHREN. Gefragt ist nach der Ähnlichkeit dieser Sequenzen.

Schreibt man die Sequenzen unter­einander, so zeigt sich, dass sie an keiner Position über­einstimmen.

Tatsächlich aber sind die Sequenzen nicht grund­verschieden, sondern sie enthalten gleiche Teilstücke, z.B. AEH und ein weiteres E, jedoch an ver­schiedener Position. Diese Über­ein­stimmung lässt sich ver­deut­lichen, indem jeweils in einer der Sequenzen Lücken (gaps) eingefügt werden.

Die Folge der an den senkrechten Strichen über­einstimmenden Buchstaben bildet die längste gemeinsame Teilsequenz (engl.: longest common subsequence) der beiden Sequenzen. Die Ausrichtung der beiden Sequenzen an der längsten gemeinsamen Teilsequenz wie oben dargestellt wird als Alignment bezeichnet.

Die Länge der längsten gemeinsamen Teilsequenz, bezogen auf die Länge der Sequenzen, ist ein Maß für die Ähnlichkeit der beiden Sequenzen. D.h. je mehr senkrechte Striche das Alignment hat, desto größer ist die Ähnlichkeit. Je mehr Nicht-Striche das Alignment dagegen hat, desto größer ist die Unter­schiedlich­keit der beiden Sequenzen.

Die Anzahl der Nicht-Striche des Alignments wird als die Editier-Distanz (engl.: edit distance) der beiden Sequenzen bezeichnet. Dieses Maß gibt an, wieviele Buchstaben-Änderungen, Einfügungen und Löschungen (= Einfügungen in der anderen Sequenz) mindestens erforderlich sind, um die eine Sequenz in die andere zu überführen. Im obigen Beispiel etwa lässt sich MAEHTE in AEHREN überführen, indem das M gelöscht wird, das T in ein R geändert wird und am Schluss ein N eingefügt wird, die Editier-Distanz ist also 3.

Die Editier-Distanz ist eine Metrik, also eine Abstands­funktion, auf der Menge der Sequenzen. Je größer der Abstand zwischen zwei Sequenzen ist, desto unter­schiedlicher sind sie.

Noch genauer lässt sich das Maß der Ähnlichkeit zweier Sequenzen fassen, wenn die Über­ein­stimmung gewisser Buchstaben höher bewertet wird als die anderer, wenn die Nicht­über­ein­stimmung bestimmter Buchstaben-Kombinationen anders bewertet wird als als die anderer, und wenn auch Einfügen und Löschen mit einer eigenen Bewertung versehen werden.

Im folgenden Beispiel bewerten wir zunächst der Einfachheit halber jede Über­ein­stimmung mit 3, jede Nicht­über­ein­stimmung mit 0, und jede Einfügung bzw. Löschung mit -1. Hierzu werden die Variablen match, mismatch und gappenalty eingeführt.

Algorithmus

Mit dem folgenden Verfahren, dem Needleman-Wunsch-Algorithmus, wird zunächst das Maß der Ähnlichkeit von zwei Sequenzen und anschließend ein Alignment berechnet [NW 70].

Gegeben sind zwei Sequenzen x und y. An die Sequenzen wird jeweils zu Anfang ein spezielles Zeichen $ angefügt. Die Längen der Sequenzen danach werden mit m bzw. n bezeichnet.

Bei der Berechnung wird eine Funktion equal benutzt, die zwei Zeichen miteinander vergleicht. Der Funktions­wert equal(i, j) ist gleich match, wenn das i-te Zeichen von x mit dem j-ten Zeichen von y über­einstimmt, und sonst gleich mismatch:

equal(i, j)  =

match     falls  xi = yj mismatch     sonst

für alle i ∈ {0, ..., m-1},  j ∈ {0, ..., n-1}.

Es wird nun eine m × n-Matrix a nach folgender Vorschrift ausgefüllt:

a_{0, 0}  =  0

a_{0, j}  =  a_{0, j-1} + gappenalty

a_{i, 0}  =  a_{i-1, 0} + gappenalty

a_{i, j}  =  max (a_{i-1, j} + gappenalty,  a_{i, j-1} + gappenalty,  a_{i-1, j-1} + equal(i, j) )

für alle i ∈ {1, ..., m-1},  j ∈ {1, ..., n-1}.

Bei der Berechnung der Einträge der Matrix wird also auf vorher berechnete andere Einträge zurück­gegriffen; diese Methode der Berechnung bezeichnet man als dynamische Pro­grammierung (engl.: dynamic programming).

Für das Beispiel ergibt sich folgende Matrix:

Die Zahl in der rechten unteren Ecke (im Beispiel die 10) ist das Maß für die Ähnlichkeit der beiden Sequenzen.

Ein Alignment der beiden Sequenzen lässt sich konstruieren, indem ausgehend vom rechten unteren Eckfeld immer in der Richtung gegangen wird, aus der das Maximum gekommen ist. Die entsprechenden Felder sind in der obigen Matrix fett gekenn­zeichnet. Wird dabei nach links gegangen, entspricht dies einer Einfügung in der Sequenz x, wird nach oben gegangen, entspricht dies einer Einfügung in der Sequenz y. Wird diagonal nach links oben gegangen, entspricht dies einer Über­ein­stimmung, wenn der Wert des aktuellen Feldes und der Wert des linken oberen Nachbar­feldes sich um match unter­scheiden, und sonst einer Nicht­über­ein­stimmung. So kommt das folgende Alignment zustande.

Implementierung

Die zu berechnende Matrix belegt einen Speicher­platz von Θ(m·n). Wenn m und n groß werden, ist dies problematisch. Zur Berechnung der Editier-Distanz, also der Zahl in der unteren Ecke der Matrix, genügt offenbar auch Θ(n) Speicher­platz, wenn die Matrix zeilenweise berechnet wird und immer nur die jeweils zuletzt berechnete Zeile gespeichert wird. Jedoch lässt sich das Alignment dann nicht mehr in der angegebenen Weise konstruieren.

Es gibt jedoch den Algorithmus von Hirschberg, der dieses Problem durch eine modifizierte Art der Berechnung löst [Hir 75].

Literatur

[HD 06]   M.T. Hütt, M. Dehnert: Methoden der Bioinformatik. Springer (2006)

[NW 70]   S.B. Needleman, C.D. Wunsch: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48, 3, 443-453 (1970)

[Hir 75]   D.S. Hirschberg: A linear space algorithm for computing maximal common subsequences. Communications of the ACM 18, 6, 341-343 (1975)