Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Open Badges Research

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

Tanja Stadler1* and James H Degnan23

Author Affiliations

1 Institute of Integrative Biology, Universitätsstrasse 16, 8092, Zürich, Switzerland

2 Department of Mathematics and Statistics, Private Bag 4800, University of Canterbury, Christchurch 8140, New Zealand

3 National Institute of Mathematical and Biological Synthesis, Knoxville, Tennessee, USA

For all author emails, please log on.

Algorithms for Molecular Biology 2012, 7:7  doi:10.1186/1748-7188-7-7

Published: 30 April 2012



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.


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.


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.

Incomplete lineage sorting; Coalescent history; Anomalous gene tree; Dynamic programming