|
Seite 20 von 77 |
Wenn ein Pfad vom Punkt (1,1) zum Punkt (n,m) der Punktmatrix gesucht wird, ist ein globales Alignment angestrebt. Die Sequenzen werden so behandelt, als seien sie über die gesamte Länge homolog.
Der bekannteste Algorithmus, der dies leistet, ist der Needleman-Wunsch-Algorithmus. Er verwendet eine Strategie, die als dynamische Programmierung bekannt ist, und nutzt die Beobachtung, dass der optimale Pfad durch inkrementelle Erweiterung von optimalen Unterpfaden gefunden werden kann.
