Paper Info
Title
Efficient computation of popular phylogenetic tree measures
Abstract
Given a phylogenetic tree $\mathcal{T}$ of n nodes, and a sample R of its tips (leaf nodes) a very common problem in ecological and evolutionary research is to evaluate a distance measure for the elements in R. Two of the most common measures of this kind are the Mean Pairwise Distance ($\ensuremath{\mathrm{MPD}} $) and the Phylogenetic Diversity ($\ensuremath{\mathrm{PD}} $). In many applications, it is often necessary to compute the expectation and standard deviation of one of these measures over all subsets of tips of $\mathcal{T}$ that have a certain size. Unfortunately, existing methods to calculate the expectation and deviation of these measures are inexact and inefficient. We present analytical expressions that lead to efficient algorithms for computing the expectation and the standard deviation of the MPD and the PD. More specifically, our main contributions are: 1 We present efficient algorithms for computing the expectation and the standard deviation of the MPD exactly, in Θ(n) time. 2 We provide a Θ(n) time algorithm for computing approximately the expectation of the PD and a O(n2) time algorithm for computing approximately the standard deviation of the PD. We also describe the major computational obstacles that hinder the exact calculation of these concepts. We also describe O(n) time algorithms for evaluating the MPD and PD given a single sample of tips. Having implemented all the presented algorithms, we assess their efficiency experimentally using as a point of reference a standard software package for processing phylogenetic trees.
Year
DOI
Venue
2012
10.1007/978-3-642-33122-0_3
WABI
Keywords
Field
DocType
standard software package,sample r,popular phylogenetic tree measure,common problem,single sample,standard deviation,common measure,phylogenetic tree,time algorithm,mean pairwise distance,efficient algorithm,efficient computation
Pairwise comparison,Combinatorics,Phylogenetic tree,Expression (mathematics),Software,Bioinformatics,Standard deviation,Mathematics,Computation
Conference
Citations 
PageRank 
References 
2
0.73
0
Authors
3
Name
Order
Citations
PageRank
Constantinos Tsirogiannis1125.93
Brody Sandel242.21
Dimitris Cheliotis321.07