Enhancing searches for optimal trees using SIESTA

Pranjal Vachaspati, Tandy Warnow

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

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

Fingerprint

Trees (mathematics)
Dynamic programming
Set theory
Data structures
Polynomials
Search Space
Dynamic Programming
Open Source
Locus
Counting
Data Structures
Polynomial time
Proportion
Branch
NP-complete problem
Optimal Solution
Subset
Optimization
Computing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Enhancing searches for optimal trees using SIESTA. / Vachaspati, Pranjal; Warnow, Tandy.

Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings. ed. / Luay Nakhleh; Joao Meidanis. Springer-Verlag, 2017. p. 232-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10562 LNBI).

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

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10562 LNBI, Springer-Verlag, pp. 232-255, 15th International Workshop on Comparative Genomics, RECOMB CG 2017, Barcelona, Spain, 10/4/17. https://doi.org/10.1007/978-3-319-67979-2_13
Vachaspati P, Warnow T. Enhancing searches for optimal trees using SIESTA. In Nakhleh L, Meidanis J, editors, Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings. Springer-Verlag. 2017. p. 232-255. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-67979-2_13
Vachaspati, Pranjal ; Warnow, Tandy. / Enhancing searches for optimal trees using SIESTA. Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings. editor / Luay Nakhleh ; Joao Meidanis. Springer-Verlag, 2017. pp. 232-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{924e989268a84b79820e97deab07750e,
title = "Enhancing searches for optimal trees using SIESTA",
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.",
author = "Pranjal Vachaspati and Tandy Warnow",
year = "2017",
month = "1",
day = "1",
doi = "10.1007/978-3-319-67979-2_13",
language = "English (US)",
isbn = "9783319679785",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "232--255",
editor = "Luay Nakhleh and Joao Meidanis",
booktitle = "Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings",

}

TY - GEN

T1 - Enhancing searches for optimal trees using SIESTA

AU - Vachaspati, Pranjal

AU - Warnow, Tandy

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

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

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

U2 - 10.1007/978-3-319-67979-2_13

DO - 10.1007/978-3-319-67979-2_13

M3 - Conference contribution

AN - SCOPUS:85030661676

SN - 9783319679785

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 232

EP - 255

BT - Comparative Genomics - 15th International Workshop, RECOMB CG 2017, Proceedings

A2 - Nakhleh, Luay

A2 - Meidanis, Joao

PB - Springer-Verlag

ER -