Using INC Within Divide-and-Conquer Phylogeny Estimation

Thien Le, Aaron Sy, Erin K. Molloy, Qiuyi (Richard) Zhang, Satish Rao, Tandy Warnow

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

Abstract

In a recent paper (Zhang, Rao, and Warnow, Algorithms for Molecular Biology 2019), the INC (incremental tree building) algorithm was presented and proven to be absolute fast converging under standard sequence evolution models. A variant of INC which allows a set of disjoint constraint trees to be provided and then uses INC to merge the constraint trees was also presented (i.e., Constrained INC). We report on a study evaluating INC on a range of simulated datasets, and show that it has very poor accuracy in comparison to standard methods. We also explore the design space for divide-and-conquer strategies for phylogeny estimation that use Constrained INC, and show modifications that provide improved accuracy. In particular, we present INC-ML, a divide-and-conquer approach to maximum likelihood (ML) estimation that comes close to the leading ML heuristics in terms of accuracy, and is more accurate than the current best distance-based methods.

Original languageEnglish (US)
Title of host publicationAlgorithms for Computational Biology - 6th International Conference, AlCoB 2019, Proceedings
EditorsCarlos Martín-Vide, Ian Holmes, Miguel A. Vega-Rodríguez
PublisherSpringer-Verlag Berlin Heidelberg
Pages167-178
Number of pages12
ISBN (Print)9783030181734
DOIs
StatePublished - Jan 1 2019
Event6th International Conference on Algorithms for Computational Biology, AlCoB 2019 - Berkeley, United States
Duration: May 28 2019May 30 2019

Publication series

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

Conference

Conference6th International Conference on Algorithms for Computational Biology, AlCoB 2019
CountryUnited States
CityBerkeley
Period5/28/195/30/19

Keywords

  • Divide-and-conquer
  • Inferring the evolutionary phylogeny of species
  • Maximum likelihood
  • Phylogeny estimation
  • Sample complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Using INC Within Divide-and-Conquer Phylogeny Estimation'. Together they form a unique fingerprint.

  • Cite this

    Le, T., Sy, A., Molloy, E. K., Zhang, Q. R., Rao, S., & Warnow, T. (2019). Using INC Within Divide-and-Conquer Phylogeny Estimation. In C. Martín-Vide, I. Holmes, & M. A. Vega-Rodríguez (Eds.), Algorithms for Computational Biology - 6th International Conference, AlCoB 2019, Proceedings (pp. 167-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11488 LNBI). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-030-18174-1_12