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

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Phylogenetic tree space can contain 'terraces' – sets of distinct topologies with identical analytical likelihood scores.
• Current phylogenetic inference software lacks efficient methods to detect, quantify, or enumerate trees on these terraces.

Purpose of the Study:

• To address the lack of efficient computational tools for analyzing terraces in phylogenetic tree space.
• To develop and implement algorithms for determining if a tree resides on a terrace, counting terrace trees, and enumerating all trees on a terrace.

Main Methods:

• Developed two independent C++ implementations of the SUPERB algorithm for terrace analysis.
• Utilized a bioinformatics programming contest format to foster efficient algorithm development.

Main Results:

• The C++ implementations are over an order of magnitude faster and use an order of magnitude less memory than previous Python implementations.
• Both C++ implementations produced identical results, ensuring reliability and accuracy.
• The developed tools efficiently handle the counting and enumeration of trees on phylogenetic terraces.

Conclusions:

• Efficient computational tools for analyzing phylogenetic terraces are now available.
• These tools can be integrated into existing phylogenetic inference software to provide more comprehensive analyses.
• The availability of these C++ implementations advances the study of phylogenetic tree space and likelihood landscapes.