Evolving Better Multiple Sequence Alignments

Luke Sheneman and James A. Foster

Abstract. Aligning multiple DNA or protein sequences is a fundamental step in the analyses of phylogeny, homology and molecular structure. Heuristic algorithms are applied because optimal multiple sequence alignment is prohibitively expensive. Heuristic alignment algorithms represent a practical trade-off between speed and accuracy, but they can be improved. We present EVALYN (EVolved ALYNments), a novel approach to multiple sequence alignment in which sequences are progressively aligned based on a guide tree optimized by a genetic algorithm. We hypothesize that a genetic algorithm can find better guide trees than traditional, deterministic clustering algorithms. We compare our novel evolutionary approach to CLUSTAL W and find that EVALYN performs consistently and significantly better as measured by a common alignment scoring technique. Additionally, we hypothesize that evolutionary guide tree optimization is inherently efficient and has less time complexity than the commonly-used neighbor-joining algorithm. We present a compelling analysis in support of this scalability hypothesis.

LNCS 3102, p. 449 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004