Bioinformatik Blog

Der Smith-Waterman-Algorithmus ermittelt lokale Alignments für zwei Sequenzen. Die Sequenzen bilden eine Matrix in der Übereinstimmungen bzw. Unterschiede bewertet werden. Ist die Matrix erstellt, wird das Feld mit der höchsten Position gesucht (können auch mehrere sein) und von dort aus diagonal die Sequenz rückwärts abgelesen, bis man auf eine 0 stößt.

Beim Smith-Waterman-Algorithmus wird ein Übereinstimmen zweier Sequenzelemente mit +2 bewertet. Gaps und Mismatches werden mit -1 bewertet. Fällt die Bewertung negativ aus, wir sie 0.

Beispiel:
Sequenz A: AAAGAGTAGT
Sequenz B: TTTTAGTTTT

D - A A A G A G T A G T
- 0 0 0 0 0 0 0 0 0 0 0
T 0 0 0 0 0 0 0 2 1 0 2
T 0 0 0 0 0 0 0 2 1 0 2
T 0 0 0 0 0 0 0 2 1 0 2
T 0 0 0 0 0 0 0 2 1 0 2
A 0 2 2 2 1 2 1 1 4 3 2
G 0 1 1 1 4 3 4 3 3 6 5
T 0 0 0 0 3 3 3 6 5 5 8 <--
T 0 0 0 0 2 2 2 5 5 4 7
T 0 0 0 0 1 1 1 4 4 4 6
T 0 0 0 0 0 0 0 3 3 3 6

Das Ergebnis ist eine maximale Bewertung von 8 (Sieh Pfeil). Das lokale Alignment liefert: T G A T

Eine Implementierung in PHP mit Quelltext gibt es hier:

(Achtung: das Backtracking habe ich hier diagonal gemacht, das entspricht nicht dem Smith-Waterman-Algorithmus)

>> Smith-Waterman-Algorithmus PHP Skript