Smith-Waterman-Algorithmus

Der Smith-Waterman-Algorithmus berechnet das optimale lokale Alignment bzw. den optimalen lokalen Alignment-Score zwischen zwei Sequenzen a und b. Er verwendet die Programmiermethode der dynamischen Programmierung.

Weiteres empfehlenswertes Fachwissen

Richtiges Wägen mit Laborwaagen: Die Wägefibel

Leitfaden zu den grundlegenden Laborkenntnissen

Wie kann man Pipetten schnell überprüfen?

Lokales Alignment Problem

Der Smith-Waterman-Algorithmus löst das lokale Alignment Problem:

Das lokale Alignment-Problem besteht darin, den Substring a' der Sequenz a und den Substring b' der Sequenz b zu finden, wobei a' und b' den maximalen globalen Alignment-Score (=Similarity-Score) haben.

Motivation

Die Berechnung des optimalen lokalen Alignment hat eine andere Anwendung als die Berechnung des optimalen globalen Alignment.

Die Betrachtung von globalen Alignments macht dort Sinn, wo man davon ausgehen kann, dass die zu vergleichenden Sequenzen relativ ähnlich sind. Z.B. Sequenzen gleicher Länge aus einer Proteinfamilie.

Wenn man allerdings nach lokalen Übereinstimmungen (=Similarities) in Sequenzen, die in anderen Bereichen sehr unterschiedlich sein können, suchen möchte, so ist die Betrachtung von lokalen Alignments sinnvoller. Denn ein optimales globales Alignment könnte in diesem Fall diese lokalen Überstimmungen verdecken, da es seinen Score in Hinblick auf die gesamte Sequenz maximieren muss, z.B. einzelne Motive in verschiedenen Proteinsequenzen.

Zusammenhang zum Needleman-Wunsch-Algorithmus

Der Needleman-Wunsch-Algorithmus berechnet das globale Alignment von zwei Sequenzen a und b. Um das lokale Alignment-Problem zu lösen sind an dem Needleman-Wunsch-Algorithmus zwei Modifikationen notwendig:

1. Initialisierung der ersten Spalte und der ersten Zeile mit 0
2. Maximierung über einen vierten Fall, nämlich 0

Der lokale Alignment-Score steht nicht in rechten unteren Ecke der Score-Matrix, sondern irgendwo in der Matrix. Es ist der Eintrag mit dem größten Wert in der Matrix.

Das optimale lokale Alignment erhält man durch Backtracking von dem A Matrix-Eintrag mit dem größten Wert bis zu einem 0-Eintrag in der Matrix.

Wie auch bei der Berechnung des globalen Alignment können auch mehrere optimale lokale Alignments von zwei Sequenzen existieren. Also können mehrere maximale Werte in der Score-Matrix existieren und für jeder optimalen Wert sind auch mehrere unterschiedliche Backtraces möglich.

Matrix-Rekurrenzen

Spezifikation des Algorithmus durch Matrix- Rekurrenzen:

• a, b = Zeichenketten ueber einem Alphabet Σ
• m = length(a)
• n = length(b)
• H(i,j) - ist der maximale Similarity-Score zwischen einem Suffix von a, welches in i endet und einem Suffix von b, welches in j endet
• , '-' der Gap-Charakter - Similarity-Score-Funktion

Effizienz

Die Laufzeit des Smith-Waterman-Algorithmus ist in O(nm) und der Speicherbedarf in O(nm). Dies kann man einfach aus den Matrix-Rekurrenzen ableiten.

Da man die Score-Matrix zeilen- bzw. spaltenweise berechnen kann, braucht man jeweils nur die aktuelle und die letzte Zeile bzw. Spalte zu speichern, wenn man nur den Score und nicht das Alignment berechnen möchte. In dem Fall liegt der Speicherbedarf in O(n) bzw. O(m).

In linearem Speicherbedarf kann man auch das lokale Alignment mit Hilfe der Programmiermethode Divide-and-Conquer berechnen. Siehe Hirschberg-Algorithmus.

Beispiel

• Sequenz 1 = ACGA
• Sequenz 2 = TCCG

• w(match) = +2
• w(a,-) = w(-,b) = w(mismatch) = -1

Für das optimale lokale Alignment wird bei der Zahl 4 begonnen und diagonal zurückgewandert. Was als Ergebnis des Alignments CG (aus Sequenz 1) mit CG (aus Sequenz 2) liefert. Dies scheint bei diesem einfachen Beispiel trivial, bei längeren Sequenzen jedoch ist das Ergebnis nicht mehr auf einen Blick aus der Angabe abzulesen.

Literatur

• T. F. Smith, M.S. Waterman. Identification of common molecular subsequences. J. Mol. Biol., 147:195-197, 1981
• D. Gusfield. Algorithms on Strings, Trees and Sequences. 11.7:232-235 , 1999, ISBN 0-521-58519-8