Der Algorithmus

Um das Problem zu lösen, verallgemeinern wir es zunächst. Gegeben zwei Strings $A=a_1 \cdots a_n$ und $B=b_1 \cdots b_m$ mit $A,B \subseteq \Sigma^*$. Wir definieren $D_{i,j}=d(a_1\cdots a_i,b_1\cdots b_j)$ als die Distanz zwischen $a_1\cdots a_i$ und $b_1 \cdots b_j$. Dann gilt folgender Satz:

Satz 1   Sei D_0,0=0, $D_{0,j}=\sum_{k=1}^{j} d(-,b_k)$, $D_{i,0}=\sum_{k=1}^{i} d(a_k,-)$. Dann gilt:

$$= \min\{$$ D_i,j D_i-1,j+d(a_i,-), D_i-1,j-1+d(a_i,b_j),

$$D_{i,j-1}+d(-,b_j) \quad\}$$

Der Wert eines optimalen globalen Alignments ist D_n,m.

Der Beweis ist einfach und wird hier exemplarisch für noch folgende ähnliche Beweise gegeben.

Beweis: Ein Alignment zwischen $a_1\cdots a_i$ und $b_1 \cdots b_j$ kann auf folgende drei Möglichkeiten enden:

1.

${\cdots a_i} \atop {\cdots -}$

2.

${\cdots a_i} \atop {\cdots b_j}$

3.

${\cdots -} \atop {\cdots b_j}$

Ein optimales Alignment, welches mit Möglichkeit 1) endet, muß Kosten D_i-1,j+d(a_i,-) haben, da der erste Teil des Alignments selbst optimal ist und $a_1\cdots a_{i-1}$ mit $b_1 \cdots b_j$ aligniert. Ein ähnliches Argument gilt für die Möglichkeiten 2) und 3).

 

  

Abbildung 14: In den beiden Problemen D_i,j und D_i-1,j erscheint das gleiche Teilproblem D_i-1,j-1.

Der Algorithmus, welcher diese Rekursion effizient löst, basiert auf dem Prinzip der dynamischen Programmierung (DP) . Ein direktes Lösen der Rekursion würde eine exponentielle Anzahl von Funktionsaufrufen beinhalten, und gewisse Teilprobleme mehrfach lösen (siehe auch Abbildung 14). Das Prinzip der dynamischen Programmierung beruht darauf, Teilprobleme genau einmal zu lösen und die Lösung zwischenzuspeichern. Mit diesen Zwischenlösungen werden dann die Lösungen von größeren Teilproblemen berechnet. Somit können wir eine $(n+1)\times (m+1)$ großes Feld D[0,n][0,m] anlegen und es dann z.B. zeilenweise füllen:

D[0][0] = 0; 
for(int i = 1; i <= n; i++)
  D[i][0] = D[i-1][0] + d(a[i],-); 
for(int j = 1; j <= m; j++)
  D[0][j] = D[0][j-1] + d(-,b[j]); 

for(int i = 1; i <= n; i++){
  for(int j = 1; j <= m; j++)
    D[i][j] = min(D[i-1][j]  + d(a[i],-),
                  D[i-1][j-1]+ d(a[i],b[j]),
                  D[i][j-1]  + d(-,b[j]));
out << D[n][m];

Beispiel 3   Betrachte die beiden Sequenzen A=WRITERS und B=VINTNER. Im folgenden wird die Tabelle zur Berechung eines optimalen Alignments mit d(a_i,b_j) = 0, falls a_i = b_j, d(a_i,b_j) = 1, sonst, angegeben.

		W	R	I	T	E	R	S
	0	1	2	3	4	5	6	7
V	1	1	2	3	4	5	6	7
I	2	2	2	2	3	4	5	6
N	3	3	3	3	3	4	5	6
T	4	4	4	4	3	4	5	6
N	5	5	5	5	4	4	5	6
E	6	6	6	6	5	4	5	6
R	7	7	6	7	6	5	4	5