Biology Reference
In-Depth Information
The vertical score can be expressed in recursive form as
V
ð
i
;
j
Þ¼
max
p
S
ð
i
p
;
j
Þþ
g
ð
p
Þ;
0
<
p
i
¼
max
f
S
ð
i
1
;
j
Þþ
a
;
max
p
S
ð
i
p
;
j
Þþ
g
ð
p
Þg;
1
<
p
i
p
0
;
p
0
þ
¼
max
f
S
ð
i
1
;
j
Þþ
a
;
max
p
0
S
ð
i
1
j
Þþ
g
ð
1
Þg;
p
0
p
0
¼
0
<
i
1
;
p
1
p
0
;
p
0
Þþ
¼
max
f
S
ð
i
1
;
j
Þþ
a
;
max
p
0
S
ð
i
1
j
Þþ
g
ð
b
g;
p
0
p
0
¼
0
<
i
1
;
p
1
p
0
¼
max
f
S
ð
i
1
;
j
Þþ
a
;
V
ð
i
1
;
j
Þþ
b
g;
0
<
i
:
(11)
1
The same recursion applies for
H
(
i
,
j
). The new recursion relation
turns out to be
S
ð
i
;
j
Þ¼
max
f
S
ð
i
1
;
j
1
Þþ
e
i;j
ð
i
1
;
j
1
Þ;
V
ð
i
;
j
Þ;
H
ð
i
;
j
Þg
V
ð
i
;
j
Þ¼
max
f
S
ð
i
1
;
j
Þþ
a
;
V
ð
i
1
;
j
Þþ
b
g
H
ð
i
;
j
Þ¼
max
f
S
ð
i
;
j
1
Þþ
a
;
H
ð
i
;
j
1
Þþ
b
g:
(12)
The modified recursive function implies that if we save the
three scoring matrices for
S
,
V
, and
H
scores, only five score
evaluations have to be performed for each cell resulting in around
5
n
2
).
j
X
jj
Y
j
calculations, which has the time complexity of
Oð
As we can see from the recursive function equation
12
to be used in
dynamic programming, only the values in cells
c
3.2.2 Sequence
Alignment in Linear-Space
ð
i
1
;
j
1
Þ
,
c
(
i
1,
j
), and
c
(
i
,
j
1) are called from the memory for calculat-
ing the optimal path score of the cell
c
(
i
,
j
). In this case, recording all
Oð
n
2
) scores is not necessary for computing the optimal alignment
score. For example, when the scores are computed by scanning each
line starting from the top-left, the active memory can only hold the
remaining required values of the previous line (i.e., scores of cells
c
(
i
), and the values computed in the
current line (i.e., scores of cells (
i
,
q
), 0
1,
p
),
j
1
p
j
Y
j
1). In this
fashion, usage of memory equal to the length of one of the
sequences is sufficient to compute
S
(
i
,
j
) in each iteration. However,
the scores computed for the optimal subpaths are lost and the
trace back phase cannot be conducted to recover an optimal path.
Hirschberg's algorithm offers a recursive procedure to recover the
optimal path for finding the longest common subsequence of two
strings. This problem is solved by the same dynamic programming
algorithm we cover, so Hirschberg's algorithm also applies to
sequence alignment [
10
].
Hirschberg's algorithm searches for an intermediate edge in an
optimal path. Once the edge is found, the optimal path problem is
q
j
