SIESTA: Enhancing Searches for Optimal Supertrees and Species Trees

Overview

Journal BMC Genomics

Publisher Biomed Central

Specialty Genetics

Date 2018 May 11

PMID 29745851

Citations 2

Authors

Pranjal Vachaspati

Tandy Warnow

Affiliations

Soon will be listed here.

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.

Citing Articles

Gentrius: Generating Trees Compatible With a Set of Unrooted Subtrees and its Application to Phylogenetic Terraces.

Chernomor O, Elgert C, von Haeseler A Mol Biol Evol. 2024; 41(11).

PMID: 39431557 PMC: 11536181. DOI: 10.1093/molbev/msae219.

Dollo-CDP: a polynomial-time algorithm for the clade-constrained large Dollo parsimony problem.

Dai J, Rubel T, Han Y, Molloy E Algorithms Mol Biol. 2024; 19(1):2.

PMID: 38191515 PMC: 10775561. DOI: 10.1186/s13015-023-00249-9.

References

Betancur-R R, Orti G . Molecular evidence for the monophyly of flatfishes (Carangimorpharia: Pleuronectiformes). Mol Phylogenet Evol. 2014; 73:18-22. DOI: 10.1016/j.ympev.2014.01.006. View

Song S, Liu L, Edwards S, Wu S . Resolving conflict in eutherian mammal phylogeny using phylogenomics and the multispecies coalescent model. Proc Natl Acad Sci U S A. 2012; 109(37):14942-7. PMC: 3443116. DOI: 10.1073/pnas.1211733109. View

Meiklejohn K, Faircloth B, Glenn T, Kimball R, Braun E . Analysis of a Rapid Evolutionary Radiation Using Ultraconserved Elements: Evidence for a Bias in Some Multispecies Coalescent Methods. Syst Biol. 2016; 65(4):612-27. DOI: 10.1093/sysbio/syw014. View

Yu Y, Warnow T, Nakhleh L . Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles. J Comput Biol. 2011; 18(11):1543-59. PMC: 3216099. DOI: 10.1089/cmb.2011.0174. View

Vachaspati P, Warnow T . FastRFS: fast and accurate Robinson-Foulds Supertrees using constrained exact optimization. Bioinformatics. 2016; 33(5):631-639. PMC: 5870905. DOI: 10.1093/bioinformatics/btw600. View

Vachaspati P, Warnow T . ASTRID: Accurate Species TRees from Internode Distances. BMC Genomics. 2015; 16 Suppl 10:S3. PMC: 4602181. DOI: 10.1186/1471-2164-16-S10-S3. View

Swenson M, Barbancon F, Warnow T, Linder C . A simulation study comparing supertree and combined analysis methods using SMIDGen. Algorithms Mol Biol. 2010; 5:8. PMC: 2837663. DOI: 10.1186/1748-7188-5-8. View

Mallo D, de Oliveira Martins L, Posada D . SimPhy: Phylogenomic Simulation of Gene, Locus, and Species Trees. Syst Biol. 2015; 65(2):334-44. PMC: 4748750. DOI: 10.1093/sysbio/syv082. View

Ronquist F, Teslenko M, van der Mark P, Ayres D, Darling A, Hohna S . MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space. Syst Biol. 2012; 61(3):539-42. PMC: 3329765. DOI: 10.1093/sysbio/sys029. View

10.

Allen J, Boyd B, Nguyen N, Vachaspati P, Warnow T, Huang D . Phylogenomics from Whole Genome Sequences Using aTRAM. Syst Biol. 2017; 66(5):786-798. DOI: 10.1093/sysbio/syw105. View

11.

Than C, Nakhleh L . Species tree inference by minimizing deep coalescences. PLoS Comput Biol. 2009; 5(9):e1000501. PMC: 2729383. DOI: 10.1371/journal.pcbi.1000501. View

12.

Tang C, Humphreys A, Fontaneto D, Barraclough T, Paradis E . Effects of phylogenetic reconstruction method on the robustness of species delimitation using single-locus data. Methods Ecol Evol. 2015; 5(10):1086-1094. PMC: 4374709. DOI: 10.1111/2041-210X.12246. View

13.

Sukumaran J, Holder M . DendroPy: a Python library for phylogenetic computing. Bioinformatics. 2010; 26(12):1569-71. DOI: 10.1093/bioinformatics/btq228. View

14.

Szollosi G, Rosikiewicz W, Boussau B, Tannier E, Daubin V . Efficient exploration of the space of reconciled gene trees. Syst Biol. 2013; 62(6):901-12. PMC: 3797637. DOI: 10.1093/sysbio/syt054. View

15.

Sharanowski B, Robbertse B, Walker J, Voss S, Yoder R, Spatafora J . Expressed sequence tags reveal Proctotrupomorpha (minus Chalcidoidea) as sister to Aculeata (Hymenoptera: Insecta). Mol Phylogenet Evol. 2010; 57(1):101-12. DOI: 10.1016/j.ympev.2010.07.006. View

16.

Akanni W, Wilkinson M, Creevey C, Foster P, Pisani D . Implementing and testing Bayesian and maximum-likelihood supertree methods in phylogenetics. R Soc Open Sci. 2015; 2(8):140436. PMC: 4555849. DOI: 10.1098/rsos.140436. View

17.

Nguyen N, Mirarab S, Warnow T . MRL and SuperFine+MRL: new supertree methods. Algorithms Mol Biol. 2012; 7(1):3. PMC: 3308190. DOI: 10.1186/1748-7188-7-3. View

18.

McMahon M, Sanderson M . Phylogenetic supermatrix analysis of GenBank sequences from 2228 papilionoid legumes. Syst Biol. 2006; 55(5):818-36. DOI: 10.1080/10635150600999150. View

19.

Mirarab S, Reaz R, Bayzid M, Zimmermann T, Swenson M, Warnow T . ASTRAL: genome-scale coalescent-based species tree estimation. Bioinformatics. 2014; 30(17):i541-8. PMC: 4147915. DOI: 10.1093/bioinformatics/btu462. View

20.

Larget B, Kotha S, Dewey C, Ane C . BUCKy: gene tree/species tree reconciliation with Bayesian concordance analysis. Bioinformatics. 2010; 26(22):2910-1. DOI: 10.1093/bioinformatics/btq539. View