TreeAlign

Several approaches to the multiple alignment problem are conceivable, but virtually all are based on the Parsimony Principle: Choose the history of a set of sequences that minimizes the overall amount of change (insertion-deletions and substitutions/mutations). This formulation was first presented by Sankoff (1 ) together with a dynamic programming algorithm solving the problem. However, this was so slow that all programs in use have opted for heuristic, but much faster algorithms, and so has TreeAlign. Given the large growth in the data involving sets of homologous sequences, a good solution to this problem has high priority.