2013/07/30 by Constantinos Tsirogiannis, Brody Sandel, Tsirogiannis, Constantinos +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Earth and Planetary Sciences · Environmental Science · #Computational Engineering #Data Structures and Algorithms (cs.DS) #Ecology and Vegetation Dynamics Studies #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Finance #Genomics and Phylogenetic Studies #Plant and Fungal Species Descriptions #Quantitative Methods (q-bio.QM) #and Science (cs.CE) #cs.CE #cs.DS #q-bio.QM
paper · pdf · doi:10.48550/arxiv.1307.7825
Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)
arxiv created 2013/07/30 · openalex publication_date 2013/07/30 · arxiv updated 2013/08/01 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The phylogenetic Mean Pairwise Distance (MPD) is one of the most popular measures for computing the phylogenetic distance between a given group of species. More specifically, for a phylogenetic tree T and for a set of species R represented by a subset of the leaf nodes of T, the MPD of R is equal to the average cost of all possible simple paths in T that connect pairs of nodes in R. Among other phylogenetic measures, the MPD is used as a tool for deciding if the species of a given group R are closely related. To do this, it is important to compute not only the value of the MPD for this group but also the expectation, the variance, and the skewness of this metric. Although efficient algorithms have been developed for computing the expectation and the variance the MPD, there has been no approach so far for computing the skewness of this measure. In the present work we describe how to compute the skewness of the MPD on a tree T optimally, in Theta(n) time; here n is the size of the tree T. So far this is the first result that leads to an exact, let alone efficient, computation of the skewness for any popular phylogenetic distance measure. Moreover, we show how we can compute in Theta(n) time several interesting quantities in T that can be possibly used as building blocks for computing efficiently the skewness of other phylogenetic measures.