Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge

Erin K. Molloy, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

Background: Divide-and-conquer methods, which divide the species set into overlapping subsets, construct a tree on each subset, and then combine the subset trees using a supertree method, provide a key algorithmic framework for boosting the scalability of phylogeny estimation methods to large datasets. Yet the use of supertree methods, which typically attempt to solve NP-hard optimization problems, limits the scalability of such approaches. Results: In this paper, we introduce a divide-and-conquer approach that does not require supertree estimation: we divide the species set into pairwise disjoint subsets, construct a tree on each subset using a base method, and then combine the subset trees using a distance matrix. For this merger step, we present a new method, called NJMerge, which is a polynomial-time extension of Neighbor Joining (NJ); thus, NJMerge can be viewed either as a method for improving traditional NJ or as a method for scaling the base method to larger datasets. We prove that NJMerge can be used to create divide-and-conquer pipelines that are statistically consistent under some models of evolution. We also report the results of an extensive simulation study evaluating NJMerge on multi-locus datasets with up to 1000 species. We found that NJMerge sometimes improved the accuracy of traditional NJ and substantially reduced the running time of three popular species tree methods (ASTRAL-III, SVDquartets, and "concatenation" using RAxML) without sacrificing accuracy. Finally, although NJMerge can fail to return a tree, in our experiments, NJMerge failed on only 11 out of 2560 test cases. Conclusions: Theoretical and empirical results suggest that NJMerge is a valuable technique for large-scale phylogeny estimation, especially when computational resources are limited. NJMerge is freely available on Github (http://github.com/ekmolloy/njmerge).

Original languageEnglish (US)
Article number14
Number of pages30
JournalAlgorithms for Molecular Biology
Volume14
Issue number1
DOIs
StatePublished - Jul 19 2019

Keywords

  • Divide-and-conquer
  • Incomplete lineage sorting
  • Neighbor Joining
  • Phylogenomics
  • Species trees

ASJC Scopus subject areas

  • Structural Biology
  • Molecular Biology
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge'. Together they form a unique fingerprint.

  • Datasets

    Data from: Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge

    Molloy, E. K. (Creator) & Warnow, T. (Creator), University of Illinois at Urbana-Champaign, May 16 2019

    Dataset

    Cite this