Problemdefinition

Als letzte Variante betrachten wir nun lokales Alignment. Im Gegensatz zum globalen Alignment sind wir hier an dem bestmöglichen Alignment von Substrings von A und B interessiert.

Beispiel 6   Bei den Werten s(a_i,b_j) = 2, falls a_i = b_j (Match), s(a_i,b_j) = -2, falls $a_i \neq b_j$ (Mismatch) und s(-,b_j) = s(a_i,-) = -1 (Indel) ist folgendes lokale Alignment für die beiden Sequenzen A=PQRAXABCSTVQ und B=XYAXBACSLL optimal (Wert : 8), d.h. es gibt kein Paar von Substrings, welches ein globales Alignment von höherem Wert hat.

                 A X A B - C S
                 A X - B A C S

Die Definition von lokalem Alignment mit Hilfe einer Distanzfunktion macht wenig Sinn, da das Ergebnis ein Alignments der Länge 1 ist (unter der Annahme einer sinnvollen Distanzfunktion).