title: Computing the skewness of the phylogenetic mean pairwise distance in linear time.
abstract: BACKGROUND
  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 [Formula: see text] and for a set of species R represented by a subset of the leaf nodes of [Formula: see text], the MPD of R is equal to the average cost of all possible simple paths in [Formula: see text] 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.
  
  
  RESULTS
  In the present work we describe how to compute the skewness of the MPD on a tree [Formula: see text] optimally, in Θ(n) time; here n is the size of the tree [Formula: see text]. 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 Θ(n) time several interesting quantities in [Formula: see text], that can be possibly used as building blocks for computing efficiently the skewness of other phylogenetic measures.
  
  
  CONCLUSIONS
  The optimal computation of the skewness of the MPD that is outlined in this work provides one more tool for studying the phylogenetic relatedness of species in large phylogenetic trees. Until now this has been infeasible, given that traditional techniques for computing the skewness are inefficient and based on inexact resampling.
authors.affiliation: MADALGO, Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University, Aarhus, Denmark ; Department of Bioscience, Aarhus University, Aarhus, Denmark.
authors.forename: Constantinos
authors.initials: C
authors.lastname: Tsirogiannis
authors.affiliation: MADALGO, Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University, Aarhus, Denmark ; Department of Bioscience, Aarhus University, Aarhus, Denmark.
authors.forename: Brody
authors.initials: B
authors.lastname: Sandel
keywords: Algorithms for phylogenetic trees; Mean pairwise distance; Skewness
references.citation: Bioinformatics. 2008 Jan 1;24(1):129-31
references.pmid: 18006550
references.citation: Microb Ecol. 2012 Jul;64(1):8-17
references.pmid: 22286378
references.citation: PLoS One. 2013;8(3):e60446
references.pmid: 23544141
references.citation: Nature. 2012 Nov 15;491(7424):444-8
references.pmid: 23123857
references.citation: Proc Biol Sci. 2008 Sep 7;275(1646):2031-7
references.pmid: 18508747
references.citation: Ecol Lett. 2014 Jul;17(7):811-20
references.pmid: 24754339
references.citation: PLoS One. 2011;6(6):e21264
references.pmid: 21731685