Biology Reference
In-Depth Information
Chapter 2
Heuristic Alignment Methods
Osamu Gotoh
Abstract
Computation of multiple sequence alignment (MSA) is usually formulated as a combinatory optimization
problem of an objective function. Solving the problem for virtually all sensible objective functions is known
to be NP-complete implying that some heuristics must be adopted. Several general strategies have been
proven effective to obtain accurate MSAs in reasonable computational costs. This chapter is devoted to a
brief summary of most successful heuristic approaches.
Key words
Multiple sequence alignment, Progressive method, Iterative refinement, Consistency
transformation, Maximal expected accuracy, Anchor, Homology extension
1
Introduction
Pairwise sequence alignment can be solved exactly by the well-
known dynamic programing algorithm. In theory, the same algo-
rithm is applicable to alignment of
N
2 sequences of average
length of
L
. However, the computational time grows in at least
O
(2
N
L
N
), so that
N
>
3 is the practical limit by this brute-force
approach. Although some elaborate algorithms have been devised
[
1
,
2
], they can hardly obtain the optimal solution when
N
ΒΌ
>
10
even for short sequences. The vastly common heuristics employed
for MSA are progressive methods. Progressive alignment is not only
used to produce preliminary MSA to be refined by the succeeding
iterative procedure but also used at the MSA construction phase
after consistency transformation applied to residue pairs to be
aligned. Rapid identification of almost certainly aligned regions
(anchors) prior to the main MSA procedure often greatly acceler-
ates overall computation. Anchoring is an inevitable step in large-
scale genomic sequence alignment and also in non-progressive
greedy MSA approaches. Thus, the progressive method, iterative
refinement, consistency transformation, and anchoring form the
major backbone of heuristic MSA algorithms. Additional informa-
tion, such as inclusion of extra homologous sequences (homology
