An O(n \log n) time Algorithm for computing the Path-length Distance\n between Trees

2018/11/01 by David Bryant, Céline Scornavacca, Bryant, David +1
Biochemistry, Genetics and Molecular Biology · Earth and Planetary Sciences · #05CO5 #68Q25 #92D15 #Data Structures and Algorithms (cs.DS) #Evolution and Paleontology Studies #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies

paper · pdf · doi:10.48550/arxiv.1811.00619

openalex publication_date 2018/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Tree comparison metrics have proven to be an invaluable aide in the\nreconstruction and analysis of phylogenetic (evolutionary) trees. The\npath-length distance between trees is a particularly attractive measure as it\nreflects differences in tree shape as well as differences between branch\nlengths. The distance equals the sum, over all pairs of taxa, of the squared\ndifferences between the lengths of the unique path connecting them in each\ntree. We describe an O(n \log n) time for computing this distance, making\nextensive use of tree decomposition techniques introduced by Brodal et al.\n(2004).\n

Related

• A Distance Metric for Tree-Sibling Time Consistent Phylogenetic Networks
• Phylogenetic tree distance computation over succinct representations
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
• A Fast Algorithm for Computing Geodesic Distances in Tree Space
• The mean value of the squared path-difference distance for rooted phylogenetic trees