Biology Reference
In-Depth Information
There are many MSA programs based on the progressive
method, such as the Clustal series [
6
], PRANK [
12
], and Kalign
[
13
].
The progressive method has a drawback in that once a gap is
incorrectly introduced, especially at an early step (near a leaf of
the guide tree), the gap is never removed in later steps. To over-
come this drawback, the iterative refinement method was proposed
[
14
-
16
]. MAFFT adopted this strategy (
see
Fig.
3
). The iterative
refinement method requires an objective function that represents
the “goodness.” An initial MSA, calculated by the progressive or
other method, is subjected to an iterative process so that the
objective function is maximized. Various objective functions and
maximization strategies have been proposed to date [
14
-
20
].
Among them, Gotoh's method with the weighted sum-of-pairs
(WSP) objective function is the most successful one. MAFFT
adopted this method in the FFT-NS-i option. In this method,
an initial MSA is partitioned into two groups, and the two groups
are re-aligned using a group-to-group alignment algorithm.
This process is repeated until no more improvements are made.
The partitions of the MSA are restricted to those corresponding to
the branches of the guide tree [
21
]. In one cycle of iterative
refinement, all the branches in the guide tree are tried as partition-
ing points. To run this option, use
2.2 Iterative
Refinement Methods
a
b
c
Group-to-group
alignment
a
b
c
d
e
d
e
Divide into
subalignments
Better score?
a
bc de
Yes
No
Tree-dependent partitioning
a
b
c
d
e
Replace
Initial alignment
Fig. 3 Outline of a fast group-to-group alignment algorithm using FFT (reprinted from [
30
]). (a) A sequence is
converted to a two-dimensional (2D) wave, arrangement of vectors. (b) A set of aligned sequences is also
converted to a 2D wave. (c) The correlation between the two waves can be rapidly computed with FFT. (d) The
highly conserved regions detected by FFT are used as anchors, and the area of the DP matrix is restricted
