|
|
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 [Allison93]
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.
This technique can be
extended [Powell et al 2000]
to linear gap costs with "small" integer costs.
|
|