TY - GEN
T1 - Enhancing searches for optimal trees using SIESTA
AU - Vachaspati, Pranjal
AU - Warnow, Tandy
N1 - Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
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
T2 - 15th International Workshop on Comparative Genomics, RECOMB CG 2017
Y2 - 4 October 2017 through 6 October 2017
ER -