World Scientific
Skip main navigation
Close Drawer MenuOpen Drawer Menu

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

During this period, the E-commerce and registration of new users may not be available for up to 6 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue — Selected Papers from the 8th International Conference on BICOB 2016; Guest Editors: N. Haspel, T. Ioerger and H. Al-Mubaid: Research PapersNo Access

Synthesizing large-scale species trees using the strict consensus approach

    https://doi.org/10.1142/S0219720017400029Cited by:3
    Previous
    Next

    Abstract

    Supertree problems are a standard tool for synthesizing large-scale species trees from a given collection of gene trees under some problem-specific objective. Unfortunately, these problems are typically NP-hard, and often remain so when their instances are restricted to rooted gene trees sampled from the same species. While a class of restricted supertree problems has been effectively addressed by the parameterized strict consensus approach, in practice, most gene trees are unrooted and sampled from different species. Here, we overcome this stringent limitation by describing efficient algorithms that are adopting the strict consensus approach to also handle unrestricted supertree problems. Finally, we demonstrate the performance of our algorithms in a comparative study with classic supertree heuristics using simulated and empirical data sets.

    References

    • 1. Arrows K , Social Choice and Individual Values, Wiley, New York, 1952. Google Scholar
    • 2. Bansal M, Eulenstein O , Algorithms for genome-scale phylogenetics using gene tree parsimony, IEEE/ACM Trans Comput Biol Bioinform 10 (4) :939–956, 2013. Crossref, Medline, Google Scholar
    • 3. Bansal M, Shamir R , A note on the fixed parameter tractability of the gene-duplication problem, IEEE/ACM Trans Comput Biol Bioinform 8 (3) :848–850, 2011. Crossref, Medline, Google Scholar
    • 4. Bininda-Emonds O , Phylogenetic Supertrees, Combining Information to Reveal the Tree of Life, Springer, Berlin, 2004. Crossref, Google Scholar
    • 5. Boykin L, Kubatko L, Lowrey T , Comparison of methods for rooting phylogenetic trees: A case study using Orcuttieae, Mol Phylogenet Evol 54 (3) :687–700, 2010. Crossref, Medline, Google Scholar
    • 6. Bryant D , A classification of consensus methods for phylogenetics, Discrete Math Theor Comput Sci 61 :163–185, 2003. Crossref, Google Scholar
    • 7. Chang W, Górecki P, Eulenstein O , Exact solutions for species tree inference from discordant gene trees, J Bioinform Comput Biol 11 (5) :1342005, 2013. Link, Google Scholar
    • 8. Cotton J, Page R , Going nuclear: Gene family evolution and vertebrate phylogeny reconciled, Proc Biol Sci 269 (1500) :1555–1561, 2002. Crossref, Medline, Google Scholar
    • 9. Day W , Optimal algorithms for comparing trees with labeled leaves, J Classif 2 (1) :7–28, 1985. Crossref, Google Scholar
    • 10. Eulenstein O, Huzurbazar S, Liberles D , Reconciling phylogenetic trees, in Evolution after Gene Duplication, Wiley, New York, 2010. Crossref, Google Scholar
    • 11. Fleischauer M, Böcker S, Collecting reliable clades using the greedy strict consensus merger, Tech Rep, PeerJ PrePrints, 2015. Google Scholar
    • 12. Goodman M et al. , Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences, Syst Biol 28 (2) :132–163, 1979. Crossref, Google Scholar
    • 13. Górecki P, Eulenstein O , A Robinson-Foulds measure to compare unrooted trees with rooted trees, ISBRA, pp. 115–126, 2012. Google Scholar
    • 14. Holland B, Penny D, Hendy M , Outgroup misplacement and phylogenetic inaccuracy under a molecular clock — A simulation study, Syst Biol 52 :229–238, 2003. Crossref, Medline, Google Scholar
    • 15. Huelsenbeck JP, Bollback JP, Levine AM , Inferring the root of a phylogenetic tree, Syst Biol 51 (1) :32–43, 2002. Crossref, Medline, Google Scholar
    • 16. Huson D, Nettles S, Warnow T , Disk-covering, a fast-converging method for phylogenetic tree reconstruction, J Comput Biol 6 (3–4) :369–386, 1999. Crossref, Medline, Google Scholar
    • 17. Jackson A , A reconciliation analysis of host switching in plant-fungal symbioses, Evolution 58 (9) :1909–1923, 2004. Crossref, Medline, Google Scholar
    • 18. Kennedy M, Page R, Prum R , Seabird supertrees: Combining partial estimates of procellariiform phylogeny, The Auk 119 (1) :88–108, 2002. Crossref, Google Scholar
    • 19. Lin H, Moon J, Eulenstein O , Consensus properties of the gene duplication problem for enhanced phylogenetic inference, BICOB, pp. 131–136, 2015. Google Scholar
    • 20. Lin H et al., Consensus properties for the deep coalescence problem and their application for scalable tree search, BMC Bioinform 13 (10) :S12, 2012. Medline, Google Scholar
    • 21. Ma B et al., From gene trees to species trees, SIAM J Comput 30 (3) :729–752, 2000. Crossref, Google Scholar
    • 22. Martin A, Burg T , Perils of paralogy: Using hsp70 genes for inferring organismal phylogenies, Syst Biol 51 (4) :570–587, 2002. Crossref, Medline, Google Scholar
    • 23. McGowen M, Clark C, Gatesy J , The vestigial olfactory receptor subgenome of odontocete whales: Phylogenetic congruence between gene-tree reconciliation and supermatrix methods, Syst Biol 57 (4) :574–590, 2008. Crossref, Medline, Google Scholar
    • 24. Moon J, Eulenstein O , Synthesizing large-scale species trees using guidance trees, BICOB, pp. 103–108, 2016. Google Scholar
    • 25. Moon J, Lin H, Eulenstein O , Consensus properties and their large-scale applications for the gene duplication problem, J Bioinform Comput Biol 14 (3) :1642005, 2016. Link, Google Scholar
    • 26. Nik-Zainal S et al., The life history of 21 breast cancers, Cell 149 (5) :994–1007, 2012. Crossref, Medline, Google Scholar
    • 27. Page R , Extracting species trees from complex gene trees: Reconciled trees and vertebrate phylogeny, Mol Phylogenet Evol 14 :89–106, 2000. Crossref, Medline, Google Scholar
    • 28. Ranwez V et al., PhySIC: A veto supertree method with desirable properties, Syst Biol 56 (5) :798–817, 2007. Crossref, Medline, Google Scholar
    • 29. Smith A , Rooting molecular trees: Problems and strategies, Biol J Linn Soc 51 :279–292, 1994. Crossref, Google Scholar
    • 30. Wehe A, Bansal M, Burleigh J, Eulenstein O , DupTree: A program for large-scale phylogenetic analyses using gene tree parsimony, Bioinform 24 (13) :1540–1541, 2008. Crossref, Medline, Google Scholar
    • 31. Wehe A, Burleigh J, Eulenstein O , Efficient algorithms for knowledge-enhanced supertree and supermatrix phylogenetic problems, IEEE/ACM Trans Comput Biol Bioinform 10 (6) :1432–1441, 2013. Crossref, Medline, Google Scholar
    • 32. Wilkinson M et al., Properties of supertree methods in the consensus setting, Syst Biol 56 (2) :330–337, 2007. Crossref, Medline, Google Scholar
    Published: 17 May 2017