DACTAL: divide-and-conquer trees (almost) without alignments.
BACKGROUND
While phylogenetic analyses of datasets containing 1000-5000 sequences are challenging for existing methods, the estimation of substantially larger phylogenies poses a problem of much greater complexity and scale.


METHODS
We present DACTAL, a method for phylogeny estimation that produces trees from unaligned sequence datasets without ever needing to estimate an alignment on the entire dataset. DACTAL combines iteration with a novel divide-and-conquer approach, so that each iteration begins with a tree produced in the prior iteration, decomposes the taxon set into overlapping subsets, estimates trees on each subset, and then combines the smaller trees into a tree on the full taxon set using a new supertree method. We prove that DACTAL is guaranteed to produce the true tree under certain conditions. We compare DACTAL to SATé and maximum likelihood trees on estimated alignments using simulated and real datasets with 1000-27 643 taxa.


RESULTS
Our studies show that on average DACTAL yields more accurate trees than the two-phase methods we studied on very large datasets that are difficult to align, and has approximately the same accuracy on the easier datasets. The comparison to SATé shows that both have the same accuracy, but that DACTAL achieves this accuracy in a fraction of the time. Furthermore, DACTAL can analyze larger datasets than SATé, including a dataset with almost 28 000 sequences.


BACKGROUND
DACTAL source code and results of dataset analyses are available at www.cs.utexas.edu/users/phylo/software/dactal.
Department of Computer Science, Calvin College, Grand Rapids, MI 49546, USA.
Serita
S
Nelesen
Kevin
K
Liu
Li-San
LS
Wang
C Randal
CR
Linder
Tandy
T
Warnow
D000465:Algorithms; D003198:Computer Simulation; D016013:Likelihood Functions; D010802:Phylogeny; D016415:Sequence Alignment; D012984:Software