Towards Integration of Multiple Alignment and Phylogenetic Tree Construction

Abstract

A central problem in the study of molecular evolution is the reconstruction of the history of a set of biological sequences in the form of a phylogenetic tree. One step in calculating this tree is the computation of a multiple alignment. Most existing approaches treat the two problems of multiple alignment and tree construction as separate while in fact they influence each other. Based on three-way alignments of pre-aligned groups of sequences we adapt a commonly used tree construction procedure to produce both tree and multiple alignment simultaneously. In contrast to existing iterative algorithms the new method can change alignments made early in the course of the computation at a later stage. A sufficient criterion to prevent the introduction of edges with negative length reduces the number of three-way alignments that need to be computed. Applications of the new approach to the alignment of protein and of nucleic acid sequences are presented.