Advancing divide-and-conquer phylogeny estimation using robinson-foulds supertrees

Xilin Yu, Thien Le, Sarah Christensen, Erin K. Molloy, Tandy Warnow

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

Abstract

One of the Grand Challenges in Science is the construction of the Tree of Life, an evolutionary tree containing several million species, spanning all life on earth. However, the construction of the Tree of Life is enormously computationally challenging, as all the current most accurate methods are either heuristics for NP-hard optimization problems or Bayesian MCMC methods that sample from tree space. One of the most promising approaches for improving scalability and accuracy for phylogeny estimation uses divide-and-conquer: a set of species is divided into overlapping subsets, trees are constructed on the subsets, and then merged together using a “supertree method”. Here, we present Exact-RFS-2, the first polynomial-time algorithm to find an optimal supertree of two trees, using the Robinson-Foulds Supertree (RFS) criterion (a major approach in supertree estimation that is related to maximum likelihood supertrees), and we prove that finding the RFS of three input trees is NP-hard. We also present GreedyRFS (a greedy heuristic that operates by repeatedly using Exact-RFS-2 on pairs of trees, until all the trees are merged into a single supertree). We evaluate Exact-RFS-2 and GreedyRFS, and show that they have better accuracy than the current leading heuristic for RFS.

Original languageEnglish (US)
Title of host publication20th International Workshop on Algorithms in Bioinformatics, WABI 2020
EditorsCarl Kingsford, Nadia Pisanti
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771610
DOIs
StatePublished - Aug 1 2020
Event20th International Workshop on Algorithms in Bioinformatics, WABI 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume172
ISSN (Print)1868-8969

Conference

Conference20th International Workshop on Algorithms in Bioinformatics, WABI 2020
CountryItaly
CityVirtual, Pisa
Period9/7/209/9/20

Keywords

  • Divide-and-conquer
  • Phylogeny estimation
  • Supertrees

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Advancing divide-and-conquer phylogeny estimation using robinson-foulds supertrees'. Together they form a unique fingerprint.

Cite this