Der Algorithmus

Der Vollständigkeit halber geben wir hier den entsprechenden Satz und Algorithmus für semi-globales Alignment an.

Satz 3   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) \quad\}$$

Der Wert eines optimalen semi-globalen Alignments ist das Maximum der Einträge in der letzten Zeile und Spalte.

Der folgende Algorithmus berechnet den Wert eines optimalen semi-globalen Alignments.

S[0][0] = 0; 
for(int i = 1; i <= n; i++)  S[i][0] = 0; 
for(int j = 1; j <= m; j++)  S[0][j] = 0; 

for(int i = 1; i <= n; i++){
  for(int j = 1; j <= m; j++)
    S[i][j] = max(S[i-1][j]  + s(a[i],-),
                  S[i-1][j-1]+ s(a[i],b[j]),
                  S[i][j-1]  + s(-,b[j]));
out << max(S[n][j] | j = 0..m, S[i][m] | i = 0..n);