|
|
Aligning three sequences is an important special case of
multiple alignment.
Each internal node in an unrooted phylogenetic
(evolutionary) tree has three neighbours,
so iterated three-way alignment is a practical way
to infer hypothetical ancestral sequences
given a number of descendant (leaf) sequences.
If the costs are "simple" {0,1}
it is possible [Allison]
to write a fast [algorithm] for this problem,
one that runs in O(n+d3)-time on average where
n is the average length of the sequences and d is the 3-way edit distance.
If the sequences are similar, d << n.
This technique can be extended
[Powell et al (ii)]
to linear gap costs (affine) with "small" integer costs.
Divide and conquer
[Powell et al (i)]
can be used to reduce the amount of space used to O(d2)
even when an optimal alignment is required.
|
|