Der Algorithmus für affine Gapkosten

Im Fall von affinen Gapkosten g(k)=a+b(k-1) hat Osamu Gotoh schon 1982 [Got82] gezeigt, daß man dieses Problem mit den gleichen Zeit- und Platzschranken lösen kann. Dies ist möglich, da sich bei einer Erweiterung eines Gaps in einer der beiden Sequenzen die gap penalty um eine Konstante b ändert. Wir definieren zusätzlich zur Ähnlichkeitsmatrix S drei sogenannte ``History''-Matrizen M,V und H mit der folgenden Bedeutung:

• M_i,j= maximale Alignmentwert eines Alignments zwischen $a_1\cdots a_i$ und $b_1 \cdots b_j$, das mit dem (Mis-)Match zwischen a_i und b_j endet.
• H_i,j= maximale Alignmentwert eines Alignments zwischen $a_1\cdots a_i$ und $b_1\cdots b_j]$, das mit dem Match zwischen einem Leerzeichen und b_j endet.
• V_i,j= maximale Alignmentwert eines Alignments zwischen $a_1\cdots a_i$ und $b_1 \cdots b_j$, das mit dem Match zwischen a_i und einem Leerzeichen endet.

Die Matrizen werden nach folgenden Vorschriften gefüllt:

$$S_{i,j} = \max\{ H_{i,j}, M_{i,j}, V_{i,j}\}$$

M_i,j = S_i-1,j-1+s(a_i,b_j)

$$H_{i,j} = \max\{ S_{i,j-1}-a, H_{i,j-1}-b\}$$

$$V_{i,j} = \max\{ S_{i-1,j}-a, V_{i-1,j}-b\}$$

Die Initialisierung der Matrizen ist in der Literatur oft falsch und benötigt einige Überlegung. In Übereinstimmung mit der Definition der drei Matrizen M,H und V. werden die Ränder wie folgt initialisiert:

M_0,0 = 0,

$$-\infty, \ 1\leq i \leq n,$$ M_i,0 =

$$-\infty, \ 1\leq j \leq m$$ M_0,j =

M gibt den maximalen Wert eines Alignments an, welches nicht mit einem Leerzeichen endet. Da es kein Alignment zwischen $a_1\cdots a_i$ und $b_1\cdots b_0$ gibt, welches nicht mit einem Leerzeichen endet, initialisieren wir M_i,0 mit dem neutralen Element unter der Operation $\max$, nämlich $-\infty$. Das gleiche Argument gilt für M_0,j. Ähnliche Argument gelten für die Matrizen V und H.

$$-g(i), \ 1\leq i \leq n,$$ V_i,0 =

$$-\infty, \ 1\leq j \leq m$$ V_0,j =

$$-\infty, \ 1\leq i \leq n,$$ H_i,0 =

$$-g(j), \ 1\leq j \leq m$$ H_0,j =

In der Literatur findet man oft folgende (falsche) Initialisierung:

$$-g(i), \ 1\leq i \leq n,$$ V_i,0 =

$$-g(j), \ 1\leq j \leq m$$ V_0,j =

$$-g(i), \ 1\leq i \leq n,$$ H_i,0 =

$$-g(j), \ 1\leq j \leq m$$ H_0,j =

In den Übungen sollen Sie anhand eines Gegenbeispiels zeigen, daß diese Initialisierung zum falschen Ergebnis führen kann. Da wir nun lediglich anstatt einer Matrix vier füllen und jeder Schritt konstante Zeit braucht, ist somit klar, daß auch Alignment mit affinen Gapkosten Zeit O(nm) braucht. Wir fassen dieses Ergebnis in folgendem Satz zusammen:

Satz 6   Das Alignment zweier Strings der Länge n und m kann unter Verwendung affiner Gapkosten in Zeit O(nm) berechnet werden. Ein optimales Alignment kann anhand der Tabelle in Zeit O(n+m) ausgegeben werden.

Wir haben nun die grundlegenden Varianten von paarweisem Alignment durchgesprochen. Es gibt zu diesem Thema eine Unmenge von weiterführenden Fragestellungen, von denen wir nur einige wenige ansprechen wollen.