Ultra-fast genome-wide inference of pairwise coalescence times

The pairwise sequentially Markovian coalescent (PSMC) algorithm and its extensions infer the coalescence time of two homologous chromosomes at each genomic position. This inference is utilized in reconstructing demographic histories, detecting selection signatures, genome-wide association studies, constructing ancestral recombination graphs and more. Inference of coalescence times between each pair of haplotypes in a large dataset is of great interest, as they may provide rich information about the population structure and history of the sample. We introduce a new method, Gamma-SMC, which is >14 times faster than current methods. To obtain this speed up, we represent the posterior coalescence time distributions succinctly as a Gamma distribution with just two parameters; while in PSMC and its extensions, these are held as a vector over discrete intervals of time. Thus, Gamma-SMC has constant time complexity per site, without dependence on a number of discrete time states. Additionally, due to this continuous representation, our method is able to infer times spanning many orders of magnitude, and as such is robust to parameter misspecification. We describe how this approach works, illustrate its performance on simulated and real data, and use it to study recent positive selection in the 1000 Genomes Project dataset.