title: A More Practical Algorithm for the Rooted Triplet Distance.
abstract: 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 [Formula: see text] time and [Formula: see text] space, where n is the number of leaf labels, has recently been implemented in the software package tqDist. In this article, we show that replacing the hierarchical decomposition tree used in Brodal et al.'s algorithm by a centroid paths-based data structure yields an [Formula: see text]-time and [Formula: see text]-space algorithm that, although slower in theory, is faster in practice as well as less memory consuming. Simulations for values of n up to 4,000,000 support our claims experimentally.
authors.affiliation: 1 Laboratory of Mathematical Bioinformatics, Institute for Chemical Research, Kyoto University , Kyoto, Japan .
authors.forename: Jesper
authors.initials: J
authors.lastname: Jansson
authors.affiliation: 2 NUS Graduate School for Integrative Sciences and Engineering, National University of Singapore , Singapore, Singapore .|3 University of Milano-Bicocca , Milano, Italy .
authors.forename: Ramesh
authors.initials: R
authors.lastname: Rajaby
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008957:Models, Genetic; D010802:Phylogeny; D012984:Software
keywords: centroid path decomposition tree; implementation; phylogenetic tree comparison; rooted triplet distance