Smith-Waterman-Algorithmus


Der Needleman-Wunsch-Algorithmus eignet sich hervorragend zum Berechnen globaler Alignments von Sequenzen ähnlicher Länge. Da jedoch eingefügte Lücken an jeder Stelle des Alignments gleich schwer "bestraft" werden, zerreißt er bei Sequenzen, deren Längen sich deutlich unterscheiden, die kürzere zugunsten einer möglichst hohen Trefferquote. Somit kann eine Sequenz mit einem oder zwei Buchstaben beginnen, auf die beliebig viele Lücken folgen - dies ist jedoch nicht länger ein sinnvolles Alignment.
Der Smith-Waterman-Algorithmus hingegen lässt Lücken zu Beginn und am Ende der kürzeren Sequenz unbestraft, so dass z.B. eine kurze Sequenz, die in einer längeren enthalten ist, genau an ihr Pendant angelagert werden kann.

Siehe auch: - Vorlesung 5: "Alignments II"
  - Probleme des Needleman-Wunsch-Algorithmus'
  - Der Smith-Waterman-Algorithmus

Water

"Water" ist ein Programm aus dem EMBOSS-Komplex, das Sequenzen mithilfe des Smith-Waterman-Algorithmus' berechnet. Hat man "Water" auf seinem Rechner installiert, kann man es mit dem Befehl "water 'dateiname'" direkt von der UNIX-Shell aus starten.