Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2018 Oct 1;34(19):3399-3401.
doi: 10.1093/bioinformatics/bty384.

Two C++ libraries for counting trees on a phylogenetic terrace

R Biczok  1 , P Bozsoky  1 , P Eisenmann  1 , J Ernst  1 , T Ribizel  1 , F Scholz  1 , A Trefzer  1 , F Weber  1 , M Hamann  1 , A Stamatakis  1   2
Affiliations

Two C++ libraries for counting trees on a phylogenetic terrace

R Biczok et al. Bioinformatics. .

Abstract

Motivation: The presence of terraces in phylogenetic tree space, i.e. a potentially large number of distinct tree topologies that have exactly the same analytical likelihood score, was first described by Sanderson et al. However, popular software tools for maximum likelihood and Bayesian phylogenetic inference do not yet routinely report, if inferred phylogenies reside on a terrace, or not. We believe, this is due to the lack of an efficient library to (i) determine if a tree resides on a terrace, (ii) calculate how many trees reside on a terrace and (iii) enumerate all trees on a terrace.

Results: In our bioinformatics practical that is set up as a programming contest we developed two efficient and independent C++ implementations of the SUPERB algorithm by Constantinescu and Sankoff (1995) for counting and enumerating trees on a terrace. Both implementations yield exactly the same results, are more than one order of magnitude faster, and require one order of magnitude less memory than a previous thirrd party python implementation.

Availability and implementation: The source codes are available under GNU GPL at https://github.com/terraphast.

Supplementary information: Supplementary data are available at Bioinformatics online.

PubMed Disclaimer

References

    1. Chernomor O. et al. (2015) Consequences of common topological rearrangements for partition trees in phylogenomic inference. J. Comput. Biol., 22, 1129–1142. - PMC - PubMed
    1. Chernomor O. et al. (2016) Terrace aware data structure for phylogenomic inference from supermatrices. Syst. Biol., 65, 997–1008. - PMC - PubMed
    1. Constantinescu M., Sankoff D. (1995) An efficient algorithm for supertrees. J. Classification, 12, 101–112.
    1. Sanderson M.J. et al. (2011) Terraces in phylogenetic tree space. Science, 333, 448–450. - PubMed
    1. Sanderson M.J. et al. (2015) Impacts of terraces on phylogenetic inference. Syst. Biol., 64, 709–726. - PubMed

Publication types