Abstract

Many supertree estimation and multi-locus species tree estimation methods compute trees by combining trees on subsets of the species set based on some NP-hard optimization criterion. A recent approach to computing large trees has been to constrain the search space by defining a set of “allowed bipartitions”, and then use dynamic programming to find provably optimal solutions in polynomial time. Several phylogenomic estimation methods, such as ASTRAL, the MDC algorithm in PhyloNet, and FastRFS, use this approach. We present SIESTA, a method that allows the dynamic programming method to return a data structure that compactly represents all the optimal trees in the search space. As a result, SIESTA provides multiple capabilities, including: (1) counting the number of optimal trees, (2) calculating consensus trees, (3) generating a random optimal tree, and (4) annotating branches in a given optimal tree by the proportion of optimal trees it appears in. SIESTA is available in open source form on github at https://github.com/pranjalv123/SIESTA.

Original languageEnglish (US)
Title of host publicationComparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings
EditorsLuay Nakhleh, Joao Meidanis
PublisherSpringer-Verlag
Pages232-255
Number of pages24
ISBN (Print)9783319679785
DOIs
StatePublished - Jan 1 2017
Event15th International Workshop on Comparative Genomics, RECOMB CG 2017 - Barcelona, Spain
Duration: Oct 4 2017Oct 6 2017

Publication series

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

Other

Other15th International Workshop on Comparative Genomics, RECOMB CG 2017
CountrySpain
CityBarcelona
Period10/4/1710/6/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Enhancing searches for optimal trees using SIESTA'. Together they form a unique fingerprint.

  • Cite this

    Vachaspati, P., & Warnow, T. (2017). Enhancing searches for optimal trees using SIESTA. In L. Nakhleh, & J. Meidanis (Eds.), Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings (pp. 232-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10562 LNBI). Springer-Verlag. https://doi.org/10.1007/978-3-319-67979-2_13