NJMerge: A Generic technique for scaling phylogeny estimation methods and its application to species trees

Erin K. Molloy, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Divide-and-conquer methods, which divide the species set into overlapping subsets, construct trees on the subsets, and then combine the 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 these approaches. In this paper, we present a new divide-and-conquer approach that does not require supertree estimation: we divide the species set into disjoint subsets, construct trees on the subsets, and then combine the trees using a distance matrix computed on the full species set. For this merger step, we present a new method, called NJMerge, which is a polynomial-time extension of the Neighbor Joining algorithm. We report on the results of an extensive simulation study evaluating NJMerge’s utility in scaling three popular species tree estimation methods: ASTRAL, SVDquartets, and concatenation analysis using RAxML. We find that NJMerge provides substantial improvements in running time without sacrificing accuracy and sometimes even improves accuracy. Furthermore, although NJMerge can sometimes fail to return a tree, the failure rate in our experiments is less than 1%. Together, these results suggest that NJMerge is a valuable technique for scaling computationally intensive methods to larger datasets, especially when computational resources are limited. NJMerge is freely available on Github: https://github.com/ekmolloy/njmerge. All datasets, scripts, and supplementary materials are freely available through the Illinois Data Bank: https://doi.org/10.13012/B2IDB-1424746_V1.

Original languageEnglish (US)
Title of host publicationComparative Genomics - 16th International Conference, RECOMB-CG 2018, Proceedings
EditorsAïda Ouangraoua, Mathieu Blanchette
PublisherSpringer-Verlag
Pages260-276
Number of pages17
ISBN (Print)9783030008338
DOIs
StatePublished - Jan 1 2018
Event16th International Conference on Comparative Genomics, RECOMB-CG 2018 - Magog-Orford, Canada
Duration: Oct 9 2018Oct 12 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11183 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Conference on Comparative Genomics, RECOMB-CG 2018
CountryCanada
CityMagog-Orford
Period10/9/1810/12/18

    Fingerprint

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Molloy, E. K., & Warnow, T. (2018). NJMerge: A Generic technique for scaling phylogeny estimation methods and its application to species trees. In A. Ouangraoua, & M. Blanchette (Eds.), Comparative Genomics - 16th International Conference, RECOMB-CG 2018, Proceedings (pp. 260-276). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11183 LNBI). Springer-Verlag. https://doi.org/10.1007/978-3-030-00834-5_15