A More Practical Algorithm for the Rooted Triplet Distance

摘要

The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist. In this paper, we show that replacing the hierarchical decomposition tree used in Brodal et al. 's algorithm by a centroid paths-based data structure yields an O(n log~3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1,000,000 support our claims experimentally.