Biology Reference
In-Depth Information
Fig. 8 Alignment matrix reduction by bounded dynamic programming (Color
figure online)
solution. Iterative deepening procedures employ naive searching
for threshold [
18
]. Iterations are repeated until the problem is
solved with increasing
starting from low values. Furthermore,
τ
regressing
after a few iterations using the alignment depth reached
at each step is known to be a more promising than the naive
approach [
19
].
τ
According to the problem definition of sequence alignment, given
M
edges of the optimal alignment path, the problem can be split
into
M
+ 1 subproblems. Perhaps, the most popular modern heur-
istics is to estimate these split points by anchoring conserved frag-
ments. A conserved fragment of length
k
indicates consecutive
diagonal edges in the alignment grid. Dynamic programming is
seeded by locating these diagonal sections as a preprocess. Employ-
ing the alignment procedures between the seed candidates restricts
the search space substantially. For example in an ideal scenario,
conserved regions are distributed uniformly throughout
3.3.3 Seeding Dynamic
Programming Using
Conserved Fragments
the
sequences resulting in average distances of adjacent seeds
'
. The
2
M
) where
is constant and
M
increases linearly with the sequence length. Of course, heuristics
leading to this great complexity reduction comes with the cost of
the difficulty in determining good seeds. To date, program series
FASTA [
20
,
21
] and BLAST [
22
,
23
] have proposed the most
accepted methods on seeded dynamic programming.
FASTA programs search for high-scoring ungapped segments
of a fixed length. This is achieved by listing all 4-6 nucleotide (for
DNA/RNA) and 1-2 amino acid (for protein) subsequences
Oð'
'
overall complexity is around
