Three Sequences

LA home
Computing
Bioinformatics
 Glossary
 Algorithms
 Alignment ||
 Compression
 Mapping
 Multiple ||
 Protein
 Three ||
 Trees
 Notes
 Three||
 Trees

  J.Th.Biol.2000
   (inc. src code)
  J.Th.Biol.1993
   & src code

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.

www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Wednesday, 22-Nov-2017 19:09:31 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.