Accelerating Wright-Fisher Forward Simulations on the Graphics Processing Unit
Preprint
Abstract
Forward Wright-Fisher simulations are powerful in their ability to model complex demography and selection scenarios, but suffer from slow execution on the CPU, thus limiting their usefulness. The single-locus Wright-Fisher forward algorithm is, however, exceedingly parallelizable, with many steps which are so-called embarrassingly parallel , consisting of a vast number of individual computations that are all independent of each other and thus capable of being performed concurrently. The rise of modern Graphics Processing Units (GPUs) and programming languages designed to leverage the inherent parallel nature of these processors have allowed researchers to dramatically speed up many programs that have such high arithmetic intensity and intrinsic concurrency. The presented G PU O ptimized Wright- Fish er simulation, or GO Fish for short, can be used to simulate arbitrary selection and demographic scenarios while running over 250-fold faster than its serial counterpart on the CPU. Even modest GPU hardware can achieve an impressive speedup of well over two orders of magnitude. With simulations so accelerated, one can not only do quick parametric bootstrapping of previously estimated parameters, but also use simulated results to calculate the likelihoods and summary statistics of demographic and selection models against real polymorphism data - all without restricting the demographic and selection scenarios that can be modeled or requiring approximations to the single-locus forward algorithm for efficiency. Further, as many of the parallel programming techniques used in this simulation can be applied to other computationally intensive algorithms important in population genetics, GO Fish serves as an exciting template for future research into accelerating computation in evolution. GO Fish is part of the Parallel PopGen Package available at: http://dl42.github.io/ParallelPopGen/Keywords
All Related Versions
- Published version: G3: Genes, Genomes, Genetics, 7 (9), 3229.
This publication has 56 references indexed in Scilit:
- SOAP3-dp: Fast, Accurate and Sensitive GPU-Based Short Read AlignerPLOS ONE, 2013
- Strong Purifying Selection at Synonymous Sites in D. melanogasterPLOS Genetics, 2013
- A Genome-Wide Scan for Breast Cancer Risk Haplotypes among African American WomenPLOS ONE, 2013
- A scalable and portable framework for massively parallel variable selection in genetic association studiesBioinformatics, 2012
- GPU-BLAST: using graphics processors to accelerate protein sequence alignmentBioinformatics, 2010
- MSMS: a coalescent simulation program including recombination, demographic structure and selection at a single locusBioinformatics, 2010
- Understanding GPU Programming for Statistical Computation: Studies in Massively Parallel Massive MixturesJournal of Computational and Graphical Statistics, 2010
- Inferring the Joint Demographic History of Multiple Populations from Multidimensional SNP Frequency DataPLOS Genetics, 2009
- Many-core algorithms for statistical phylogeneticsBioinformatics, 2009
- A flexible forward simulator for populations subject to selection and demographyBioinformatics, 2008