SATé-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees

Highly accurate estimation of phylogenetic trees for large datasets is difficult, in part because multiple sequence alignments must be accurate for phylogeny estimation methods to be accurate. Co-estimation of alignments and trees has been attempted, but currently only SATé estimates reasonably accurate trees and alignments for large datasets in practical time frames (Liu et al., 2009b). Here, we present a modification to the original SATé algorithm that improves upon SATé (which we now call SATé-I) in terms of speed and of phylogenetic and alignment accuracy. SATé-II uses a different divide-and-conquer strategy than SATé-I, and so produces smaller, more closely related subsets than SATé-I; as a result, SATé-II produces more accurate alignments and trees, can analyze larger datasets, and runs more efficiently than SATé-I. SATé-II is a meta-method that takes an existing multiple sequence alignment method as an input parameter and boosts the quality of that alignment method. SATé-II-boost...