Der Algorithmus

Auf den ersten Blick erscheint lokales Alignment als ein schwierigeres Problem als globales, da wir die Ähnlichkeit zwischen Paaren von beliebigen Substrings maximieren wollen. Eine direkte Lösung des Problems könnte auch darin bestehen, für alle Paare von Substrings ein optimales globales Alignment zu berechnen, ein Verfahren, welches eine Zeitkomplexität von O(n³m³) hat.

Wir werden jedoch zeigen, das auch ein lokales Alignment mit einer geringfügigen Änderung des semi-globalen Algorithmus in Zeit O(nm) berechnet werden kann. In der Rekursionsgleichung kommt noch ein weiterer Fall hinzu und es gilt:

Satz 4   Sei S_0,0 = 0, S_0,j = 0, S_i,0 = 0. Dann gilt:

$$= \max\{$$ S_i,j S_i-1,j + s(a_i,-), S_i-1,j-1+s(a_i,b_j), S_i,j-1 +s(-,b_j),

$$0 \quad\}$$

Der Wert eines optimalen lokalen Alignments ist der maximale Wert der Matrix.

Für jeden Eintrag (i,j) in der Tabelle gilt, daß es immer ein Alignment von leeren Suffixen von $a_1\cdots a_i$ und $b_1 \cdots b_j$ mit Wert 0 gibt. Aus diesem Grund sind alle Einträge in der Tabelle immer größer gleich 0. Wenn also Präfixe der beiden Sequenzen nicht gut aligniert werden können, so kann man die Berechnung durch den Wert 0 praktisch neu initialisieren und die Präfixe ignorieren.

Das gleiche Argument gilt für schlecht zu alignierende Suffixe der beiden Sequenzen. Durch die Wahl des maximalen Wertes der gesamten Matrix lassen wir keine Verschlechterung des Alignmentwertes durch diese Suffixe zu.

Beispiel 7   Betrachte die beiden Sequenzen A=TTGCTCCA und B=ACCTCGCCGT. Im folgenden wird die Tabelle zur Berechung eines optimalen Alignments mit s(a_i,b_j) = 2, falls a_i = b_j, s(a_i,b_j) = -2, falls $a_i \neq b_j$ und s(-,b_j) = s(a_i,-) = -1 angegeben.

		T	T	G	C	T	C	C	A
	0	0	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0	0	2
C	0	0	0	0	2	0	2	2	1
C	0	0	0	0	2	1	2	4	3
T	0	2	2	1	1	4	3	3	2
C	0	1	1	0	3	3	6	5	4
G	0	0	0	3	2	2	5	4	3
C	0	0	0	2	5	4	4	7	6
C	0	0	0	1	4	3	6	6	5
G	0	0	0	2	3	2	5	5	4
T	0	2	2	1	2	5	4	4	3

Der Traceback  läuft nun vom maximalen Matrixelement bis zur ersten 0. In dem Beispiel liefert er uns das optimale lokale Alignment:

                 C T C - C
                 C T C G C

mit Wert 7.