Three Sequences |
|
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, This technique can be extended
Divide and conquer
|
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Thursday, 18-Apr-2024 08:09:39 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |