Dataset Information

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

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.

SUBMITTER: Biczok R

PROVIDER: S-EPMC6157082 | biostudies-other | 2018 Oct

REPOSITORIES: biostudies-other

ACCESS DATA

Publications

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

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

Bioinformatics (Oxford, England) 20181001 19

<h4>Motivation</h4>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 ...[more]

PMID: 29746618

Similar Datasets

Project description:Phylogenetic analysis is used to analyze the evolution of species according to the characteristics of biological sequences. The analytical results are generally represented by phylogenetic trees. NJ (neighbor joining) is a frequently used algorithm for constructing phylogenetic trees because of its few assumptions, fast operation, and high accuracy, and is based on the distance between taxa. It is known that NJ usually constructs different phylogenetic trees for the same dataset with differences in input order, which are known as “tied trees.” This article proposes an improved method of NJ, called ENJ (extended neighbor joining). The ENJ can join several (currently limited to three) nodes with the same minimum distance into a new node, rather than joining two nodes in one iteration, so it can construct triple phylogenetic trees. We have inferred the formulas for updating the distance values and calculating the branch lengths for the ENJ algorithm. We have tested the ENJ with simulated and real data. The experimental results show that, compared with other methods, the trees constructed by the ENJ have greater similarity to the initial trees, and the ENJ is much faster than the NJ algorithm. Moreover, we have constructed a phylogenetic tree for the novel coronavirus (COVID-19) and related coronaviruses by ENJ, which shows that COVID-19 and SARS-CoV are closer than other coronaviruses. Because it differs from the existing phylogenetic trees for those coronaviruses, we constructed a phylogenetic network for them. The network shows those species have had a reticulate evolution. Graphical Abstract Accurately inferring evolutionary relationships between species can help humans to understand the evolutionary history and the mechanism. ENJ is an efficient and effective algorithm for constructing phylogenetic trees, which can construct triple phylogenetic trees, if necessary. The trees constructed by ENJ can better describe the original information and reflect the real evolutionary relationship of species.

Dataset Information

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

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets