Improving progressive alignment for phylogeny reconstruction using parsimonious guide-trees

Phytogenies are widely used for understanding the evolutionary histories of species and gene products. Maximum parsimony (MP) and maximum likelihood (ML) are commonly used optimization criteria for constructing phylogenies. However, phylogenetic descriptions depend not only on the employed reconstruction technique, but also on the underlying sequence alignment. Here, we establish a simple prescription to improve the underlying alignments used in phytogeny reconstruction. We adapt Gotoh's iterative strategy for improving a progressive alignment (by using better guide-trees) specifically for the purpose of constructing optimal MP phylogenies. We improve the progressive alignment heuristic as implemented in the MUSCLE alignment program by iterating with maximum parsimony guide-trees constructed using PAUP*, yielding both deterministic and randomized heuristics. We evaluate accuracy on simulated data under a wide range of model conditions and show that phylogenies produced using our technique are more accurate than phylogenies on other alignments.