In this talk, we present TERADACTAL, a novel divide-and-conquer approach for estimating large evolutionary trees. Phylogeny estimation from sequence data typically involves two computationally intensive tasks: constructing a multiple sequence alignment and then building a maximum likelihood tree. Using this two-phase approach to analyze ultra-large datasets requires enormous computational resources (weeks to years of CPU time and hundreds of GBs of storage). TERADACTAL differs from prior approaches by avoiding (1) alignment estimation on the full dataset, (2) maximum likelihood tree estimation on the full dataset, and (3) supertree estimation (which under a variety of optimization criteria is NP-hard). This is accomplished through our new highly accurate and parallelizable technique for merging trees built from subsets of the data. Finally, we present the results of a simulation study (performed on Blue Waters) demonstrating that TERADACTAL achieves similar accuracy to the leading two-phase methods. Thus, TERADACTAL provides a breakthrough in parallel algorithm design for ultra-large phylogeny estimation.
