Problemdefinition

Bisher beschäftigten wir uns nur mit Alignments, in deren Zielfunktionen wir Matches , Mismatches  und Indels  betrachteten. In der Praxis werden diese Alignments kaum benutzt, hier erweitert man das Alignment-Modell um gaps.

Definition 2   Ein gap ist ein maximaler Substring $x'_i\cdots x'_j$ für X=A oder X=B in einem Alignment von A und B, welcher nur aus Leerzeichen besteht, d.h. x'_k = '-', für $i\leq k \leq j$.

Gaps erlauben uns, Alignments zu berechnen, welche besser den zugrundeliegenden biologischen Modellen entsprechen. Wir definieren nun eine neue Rekursion für globales Ähnlichkeitsalignment mit gaps, wobei g(k)>0 die Kosten eines Gaps der Länge k angeben:

Satz 5   Sei S_0,0 = 0, S_0,j = -g(j), S_i,0 = -g(i). Dann gilt:

$$= \max\{ \max_{1\leq l\leq i} S_{i-l,j} - g(l),$$ S_i,j S_i-1,j-1+s(a_i,b_j),

$$\max_{1 \leq k \leq j} S_{i,j-k} -g(k) \quad\}$$

Der Wert eines optimalen globalen Alignments ist S_n,m.