Research
A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree
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
Algorithms for Molecular Biology 2012, 7:7 doi:10.1186/1748-7188-7-7
Published: 30 April 2012Abstract
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.
