# Brody Steven Sandel

## Efficient Computation of Popular Phylogenetic Tree Measures

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer review

• Constantinos Tsirogiannis, Danmark
• Brody Steven Sandel
• Dimitris Cheliotis, Department of Mathematics, University of Athens, Grækenland

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:

We present efficient algorithms for computing the expectation and the standard deviation of the MPD exactly, in Θ(n) time. 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.

Originalsprog Engelsk Lecture Notes in Computer Science 7534 30-43 30 0302-9743 https://doi.org/10.1007/978-3-642-33122-0_3 Udgivet - 2012 International Workshop on Algorithms in Bioinformatics - Ljubljana, SlovenienVarighed: 10 sep. 2012 → 12 sep. 2012Konferencens nummer: 12

### Konference

Konference International Workshop on Algorithms in Bioinformatics 12 Slovenien Ljubljana 10/09/2012 → 12/09/2012

Citationsformater

Indlæser lokationer...

ID: 51957687

1382 / i36