Back to overview

A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Publication date 2012
Author Stadler Tanja, Degnan James H.,
Project Estimating epidemiological and evolutionary parameters from viral sequence data using phylogenetic methods
Show all

Original article (peer-reviewed)

Journal Algorithms for Molecular Biology
Volume (Issue) 7(1)
Page(s) 1
Title of proceedings Algorithms for Molecular Biology
DOI 10.1186/1748-7188-7-7


Background: The ancestries of genes form gene trees which do not necessarily have the same topology as the species tree due to incomplete lineage sorting. Available algorithms determining the probability of a gene tree given a species tree require exponential computational runtime.Results: In this paper, we provide a polynomial time algorithm to calculate the probability of a ranked gene tree topology for a given species tree, where a ranked tree topology is a tree topology with the internal vertices being ordered. The probability of a gene tree topology can thus be calculated in polynomial time if the number of orderings of the internal vertices is a polynomial number. However, the complexity of calculating the probability of a gene tree topology with an exponential number of rankings for a given species tree remains unknown.Conclusions: Polynomial algorithms for calculating ranked gene tree probabilities may become useful in developing methodology to infer species trees based on a collection of gene trees, leading to a more accurate reconstruction of ancestral species relationships. © 2012 Stadler and Degnan; licensee BioMed Central Ltd.