Aarhus University Seal / Aarhus Universitets segl

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.

OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind7534
Sider (fra-til)30-43
Antal sider30
ISSN0302-9743
DOI
StatusUdgivet - 2012
BegivenhedInternational Workshop on Algorithms in Bioinformatics - Ljubljana, Slovenien
Varighed: 10 sep. 201212 sep. 2012
Konferencens nummer: 12

Konference

KonferenceInternational Workshop on Algorithms in Bioinformatics
Nummer12
LandSlovenien
ByLjubljana
Periode10/09/201212/09/2012

Se relationer på Aarhus Universitet Citationsformater

ID: 51957687

1382 / i36