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 s...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-05-01
|
| Series: | BMC Genomics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12864-018-4621-1 |
| _version_ | 1818525224313815040 |
|---|---|
| author | Pranjal Vachaspati Tandy Warnow |
| author_facet | Pranjal Vachaspati Tandy Warnow |
| author_sort | Pranjal Vachaspati |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T06:06:41Z |
| format | Article |
| id | doaj.art-2e1cdb5f1ebe482f88d947d5f7b74e1f |
| institution | Directory Open Access Journal |
| issn | 1471-2164 |
| language | English |
| last_indexed | 2024-12-11T06:06:41Z |
| publishDate | 2018-05-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Genomics |
| spelling | doaj.art-2e1cdb5f1ebe482f88d947d5f7b74e1f2022-12-22T01:18:16ZengBMCBMC Genomics1471-21642018-05-0119S5415710.1186/s12864-018-4621-1SIESTA: enhancing searches for optimal supertrees and species treesPranjal Vachaspati0Tandy Warnow1Department of Computer Science, University of Illinois at Urbana-ChampaignDepartment of Computer Science, University of Illinois at Urbana-ChampaignAbstract 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.http://link.springer.com/article/10.1186/s12864-018-4621-1PhylogenomicsSpecies treesDynamic programmingASTRALNP-hard problemsSupertree methods |
| spellingShingle | Pranjal Vachaspati Tandy Warnow SIESTA: enhancing searches for optimal supertrees and species trees BMC Genomics Phylogenomics Species trees Dynamic programming ASTRAL NP-hard problems Supertree methods |
| title | SIESTA: enhancing searches for optimal supertrees and species trees |
| title_full | SIESTA: enhancing searches for optimal supertrees and species trees |
| title_fullStr | SIESTA: enhancing searches for optimal supertrees and species trees |
| title_full_unstemmed | SIESTA: enhancing searches for optimal supertrees and species trees |
| title_short | SIESTA: enhancing searches for optimal supertrees and species trees |
| title_sort | siesta enhancing searches for optimal supertrees and species trees |
| topic | Phylogenomics Species trees Dynamic programming ASTRAL NP-hard problems Supertree methods |
| url | http://link.springer.com/article/10.1186/s12864-018-4621-1 |
| work_keys_str_mv | AT pranjalvachaspati siestaenhancingsearchesforoptimalsupertreesandspeciestrees AT tandywarnow siestaenhancingsearchesforoptimalsupertreesandspeciestrees |