Exact Coalescent Likelihoods by an Accelerated Recursion

A sample of DNA sequences carries the history of how they descended from a common ancestor, but that history, the genealogy, is never observed. The likelihood of the sample averages over every genealogy it could have had, and inference about mutation rates and population history rests on it. Under the infinite-sites model the likelihood can be computed exactly by the Griffiths-Tavaré recursion, the yardstick against which approximate methods such as importance sampling are measured. The recursion, however, visits every ancestral configuration of the sample, and its limit is memory rather than arithmetic: on the standard benchmark of 55 mitochondrial sequences, with 218 million configurations, the exact likelihood took about 28 hours on one processor. This talk presents an accelerated recursion that jumps from one mutation to the next, summing each run of coalescences in closed form, and shows why it is exact. Holding the much smaller graph of the recursion’s shapes in memory lets every table of probabilities be bounded before evaluation and released as soon as it has been read, and the computation runs in parallel across processors. The benchmark then fits in 0.45 GB, and exact likelihoods come within reach for samples with up to 11 billion configurations, fifty times the benchmark. Joint work with John L.Spouge (NCBI).