1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
/***
Needleman-Wunch recursions
Notation: i,j are prefix lengths so are in
ranges i = [0,|A|) and j = [0,|B|].
Profile positions are in ranges [0,|A|-1]
and [0,|B|-1] so prefix length i corresponds
to position (i-1) in the profile, and similarly
for j.
Terminal gap scoring
--------------------
Terminal gaps are scored as with open [close]
penalties only at the left [right] terminal,
as follows:
0 i
| |
A XXXXX...
B ---XX...
i |A|-1
| |
A ...XXXXX
B ...XX---
In these examples, open / close penalty at position
i is included, but close / open penalty at |A|-1 /
0 is not included.
This is implemented by setting the open [close]
penalty to zero in the first [last] position of
each profile.
Consider adding a column to a sub-alignment. After the
column is added, there are i letters from A and j letters
from B.
The column starts a left-terminal gap if:
Delete with i=1, j=0 or
Insert with i=0, j=1.
The column ends a left-terminal gap if:
Match following Delete with j=1, or
Match following Insert with i=1.
The column starts a right-terminal gap if:
Delete following a Match and i=|A|, or
Insert following a Match and j=|B|.
The column ends a right-terminal gap if:
Match with i=|A|, j=|B| following Delete or Insert.
RECURSION RELATIONS
===================
i-1
|
DD A ..X X
B ..- -
MD A ..X X
B ..X -
D(i,j) = max
D(i-1,j) + e
M(i-1,j) + goA(i-1)
Valid for:
i = [1,|A|-1]
j = [1,|B|]
I(i,j) By symmetry with D(i,j).
i-2
| i-1
| |
MM A ..X X
B ..X X
DM A ..X X
B ..- X
IM A ..- X
B ..X X
| |
| j-1
j-2
M(i,j) = L(i-1,j-1) + max
M(i-1,j-1)
D(i-1,j-1) + gcA(i-2)
I(i-1,j-1) + gcB(j-2)
Valid for:
i = [2,|A|]
j = [2,|B|]
Equivalently:
M(i+1,j+1) = L(i,j) + max
M(i,j)
D(i,j) + gcA(i-1)
I(i,j) + gcB(j-1)
Valid for:
i = [1,|A|-1]
j = [1,|B|-1]
Boundary conditions
===================
A XXXX
B ----
D(0,0) = -infinity
D(i,0) = ie
i = [1,|A|]
D(0,j) = -infinity
j = [0,|B|]
I(0,0), I(0,j) and I(i,0) by symmetry with D.
M(0,0) = 0
M(i,0) = -infinity, i > 0
M(0,j) = -infinity, j > 0
A X
B -
D(1,0) = e
D(1,j) = -infinity, j = [1,|B|]
(assuming no I-D allowed).
D(0,1) = -infinity
D(1,1) = -infinity
D(i,1) = max.
***/
|
