|
Seite 21 von 77 |
Eine Modifikation des Needleman-Wunsch-Algorithmus erlaubt lokale Alignments. Diese Modifikation ist als Smith-Waterman-Algorithmus bekannt, wobei der Pfad nicht wie bei globalen Alignments die Ecken der Punktmatrix erreichen muss. Der Algorithmus benutzt dabei ein Bewertungssystem (scoring). Der berechnete Wert für den Pfad sinkt, wenn er in Regionen geringer Ähnlichkeit hinein erweitert wird.
Wenn der Wert unter einen bestimmten Schwellenwert sinkt, wird die Verlängerung des Pfades abgebrochen. Ein neuer Pfad kann dann begonnen werden.
Der Pfad mit dem besten Gesamtergebnis wird als optimales lokales Alignment ausgegeben. Dieser stellt ein so genanntes High-scoring Segment Pair (HSP) dar. Es besteht aus jeweils einem Fragment der Abfragesequenz und einem der Vergleichsequenz,und ist in seiner Länge durch das oben erwähnte Bewertungssystem bestimmt.
