Research

Auto-validating von Neumann rejection sampling from small phylogenetic tree spaces

Raazesh Sainudiin^1,2 and Thomas York^3,4

¹  Department of Statistics, University of Oxford, Oxford, OX1 3TG, UK

²  Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch, New Zealand

³  Department of Biological Statistics and Computational Biology, Cornell University, Ithaca, New York 14853, USA

⁴  Boyce Thompson Institute for Plant Research, Cornell University, Ithaca, New York 14853, USA

author email corresponding author email

Algorithms for Molecular Biology 2009, 4:1doi:10.1186/1748-7188-4-1

Published:	7 January 2009

Abstract

Background

In phylogenetic inference one is interested in obtaining samples from the posterior distribution over the tree space on the basis of some observed DNA sequence data. One of the simplest sampling methods is the rejection sampler due to von Neumann. Here we introduce an auto-validating version of the rejection sampler, via interval analysis, to rigorously draw samples from posterior distributions over small phylogenetic tree spaces.

Results

The posterior samples from the auto-validating sampler are used to rigorously (i) estimate posterior probabilities for different rooted topologies based on mitochondrial DNA from human, chimpanzee and gorilla, (ii) conduct a non-parametric test of rate variation between protein-coding and tRNA-coding sites from three primates and (iii) obtain a posterior estimate of the human-neanderthal divergence time.

Conclusion

This solves the open problem of rigorously drawing independent and identically distributed samples from the posterior distribution over rooted and unrooted small tree spaces (3 or 4 taxa) based on any multiply-aligned sequence data.