Abstract

Background: 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, FastRFS, and ALE, use this approach. Results: We present SIESTA, a method that can be combined with these dynamic programming algorithms 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. Conclusions: SIESTA improves the accuracy of FastRFS and ASTRAL, and is a general technique for enhancing dynamic programming methods for constrained optimization.

Original languageEnglish (US)
Article number252
JournalBMC genomics
Volume19
DOIs
StatePublished - May 8 2018

Keywords

  • ASTRAL
  • Dynamic programming
  • NP-hard problems
  • Phylogenomics
  • Species trees
  • Supertree methods

ASJC Scopus subject areas

  • Biotechnology
  • Genetics

Cite this

SIESTA : Enhancing searches for optimal supertrees and species trees. / Vachaspati, Pranjal; Warnow, Tandy.

In: BMC genomics, Vol. 19, 252, 08.05.2018.

Research output: Contribution to journalArticle

@article{5e5437b55b494ff7922a305e70d720dd,
title = "SIESTA: Enhancing searches for optimal supertrees and species trees",
abstract = "Background: 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, FastRFS, and ALE, use this approach. Results: We present SIESTA, a method that can be combined with these dynamic programming algorithms 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. Conclusions: SIESTA improves the accuracy of FastRFS and ASTRAL, and is a general technique for enhancing dynamic programming methods for constrained optimization.",
keywords = "ASTRAL, Dynamic programming, NP-hard problems, Phylogenomics, Species trees, Supertree methods",
author = "Pranjal Vachaspati and Tandy Warnow",
year = "2018",
month = "5",
day = "8",
doi = "10.1186/s12864-018-4621-1",
language = "English (US)",
volume = "19",
journal = "BMC Genomics",
issn = "1471-2164",
publisher = "BioMed Central",

}

TY - JOUR

T1 - SIESTA

T2 - Enhancing searches for optimal supertrees and species trees

AU - Vachaspati, Pranjal

AU - Warnow, Tandy

PY - 2018/5/8

Y1 - 2018/5/8

N2 - Background: 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, FastRFS, and ALE, use this approach. Results: We present SIESTA, a method that can be combined with these dynamic programming algorithms 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. Conclusions: SIESTA improves the accuracy of FastRFS and ASTRAL, and is a general technique for enhancing dynamic programming methods for constrained optimization.

AB - Background: 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, FastRFS, and ALE, use this approach. Results: We present SIESTA, a method that can be combined with these dynamic programming algorithms 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. Conclusions: SIESTA improves the accuracy of FastRFS and ASTRAL, and is a general technique for enhancing dynamic programming methods for constrained optimization.

KW - ASTRAL

KW - Dynamic programming

KW - NP-hard problems

KW - Phylogenomics

KW - Species trees

KW - Supertree methods

UR - http://www.scopus.com/inward/record.url?scp=85046654830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046654830&partnerID=8YFLogxK

U2 - 10.1186/s12864-018-4621-1

DO - 10.1186/s12864-018-4621-1

M3 - Article

C2 - 29745851

AN - SCOPUS:85046654830

VL - 19

JO - BMC Genomics

JF - BMC Genomics

SN - 1471-2164

M1 - 252

ER -