Biology Reference
In-Depth Information
Fig. 7 Subproblem division in Hirschberg's algorithm
divided into subproblems as the search for the optimal path section
before this edge and the search for the section after it. Recursive
repetition of the same procedure for the intermediate edges in the
subsections is performed until the all intermediate edges are found.
A typical application is as follows. Assume the procedure attempt-
ing to find the edge contained in the optimal path, where the path is
crossing the median row of the alignment grid. To search for this
edge, similar forward and backward score computations are
performed as in finding the near-optimal paths described previ-
ously. In this case the
S
F
(
i
,
j
), 0
i
< bj
X
j
/2
c
,0
j
j
Y
j
,
and
S
R
(
i
,
j
),
are computed.
The maximal path score is found by looking for the highest score
S
F
bj
X
j
/2
c
i
j
X
j
,0
j
j
Y
j
and the
corresponding edge belongs to the optimal path. The same proce-
dure is employed for the median of the two subproblems (i.e.,
to find the optimal path edges crossing rows
ðbj
X
j=
2
c
1
;
q
Þþ
e
bjXj=
2
c;j
ðbj
X
j=
2
c;
q
Þþ
S
R
ðbj
X
j=
2
c;
j
Þ
bj
X
j
/4
c
, and
b
). All non-horizontal paths are discovered following
this binary fashion, and finally the optimal path is completed by
remaining horizontal edges. At
k
th recursion, 2
k
subproblems are
defined. From Fig.
7
, it can be seen that each subproblem has half
number of rows (and columns) of the previous one (i.e., the upper-
left submatrix and the lower-right submatrix have half of the cells
contained in the current matrix). Due to quadratic complexity, a
subproblem requires (2
k
)
2
fold less computation than the original
problem. Therefore, the number of total computations required in
the recursive procedure is at most
3
j
X
j
/4
c
2
4
þþ
2
k
4
k
þ
S
Hirschberg
¼
S
þ
0
k
(13)
¼
2
S
;
where
is the amount computation required for the original prob-
lem. While the computation is multiplied by a constant factor, and
the algorithm still has quadratic complexity, only the scores of the
median lines are required to find the median edges. As we know
S
