A More Practical Algorithm for the Rooted Triplet Distance.

Area of Science:

• Computational Biology
• Phylogenetics
• Algorithm Analysis

Background:

• The rooted triplet distance quantifies dissimilarities between phylogenetic trees.
• An existing O(n) algorithm by Brodal et al. has been implemented in tqDist.
• Efficient computation is crucial for large-scale phylogenetic analyses.

Purpose of the Study:

• To develop a more practical and memory-efficient algorithm for rooted triplet distance calculation.
• To improve upon the theoretical and empirical performance of existing methods.

Main Methods:

• Replaced the hierarchical decomposition tree in Brodal et al.'s algorithm with a centroid paths-based data structure.
• Developed a new algorithm with theoretical time complexity of O(n log n) and space complexity of O(n).
• Conducted simulations with up to 4,000,000 leaf labels to validate performance.

Main Results:

• The new centroid paths-based algorithm demonstrates superior practical performance compared to the O(n) algorithm.
• The improved algorithm is faster and consumes less memory in empirical tests.
• Simulations confirm the practical advantages for large values of n.

Conclusions:

• The centroid paths-based approach offers a more efficient practical solution for computing rooted triplet distances.
• This advancement is beneficial for large-scale phylogenetic tree comparisons.
• The findings suggest a valuable alternative for computational phylogenetics software.