2 Needleman-Wunch recursions
\r
4 Notation: i,j are prefix lengths so are in
\r
5 ranges i = [0,|A|] and j = [0,|B|].
\r
7 Profile positions are in ranges [0,|A|-1]
\r
8 and [0,|B|-1] so prefix length i corresponds
\r
9 to position (i-1) in the profile, and similarly
\r
12 Terminal gap scoring
\r
13 --------------------
\r
14 Terminal gaps are scored as with open [close]
\r
15 penalties only at the left [right] terminal,
\r
28 In these examples, open / close penalty at position
\r
29 i is included, but close / open penalty at |A|-1 /
\r
32 This is implemented by setting the open [close]
\r
33 penalty to zero in the first [last] position of
\r
36 Consider adding a column to a sub-alignment. After the
\r
37 column is added, there are i letters from A and j letters
\r
40 The column starts a left-terminal gap if:
\r
41 Delete with i=1, j=0 or
\r
42 Insert with i=0, j=1.
\r
44 The column ends a left-terminal gap if:
\r
45 Match following Delete with j=1, or
\r
46 Match following Insert with i=1.
\r
48 The column starts a right-terminal gap if:
\r
49 Delete following a Match and i=|A|, or
\r
50 Insert following a Match and j=|B|.
\r
52 The column ends a right-terminal gap if:
\r
53 Match with i=|A|, j=|B| following Delete or Insert.
\r
73 I(i,j) By symmetry with D(i,j).
\r
90 M(i,j) = L(i-1,j-1) + max
\r
92 D(i-1,j-1) + gcA(i-2)
\r
93 I(i-1,j-1) + gcB(j-2)
\r
100 M(i+1,j+1) = L(i,j) + max
\r
109 Boundary conditions
\r
110 ===================
\r
122 I(0,0), I(0,j) and I(i,0) by symmetry with D.
\r
125 M(i,0) = -infinity, i > 0
\r
126 M(0,j) = -infinity, j > 0
\r
131 D(1,j) = -infinity, j = [1,|B|]
\r
132 (assuming no I-D allowed).
\r