%0 Journal Article %1 Padhukasahasram_2008 %A Padhukasahasram, B. %A Marjoram, P. %A Wall, J. D. %A Bustamante, C. D. %A Nordborg, M. %D 2008 %I Genetics Society of America %J Genetics %K ARG forwards_time methods simulation software %N 4 %P 2417--2427 %R 10.1534/genetics.107.085332 %T Exploring Population Genetic Models With Recombination Using Efficient Forward-Time Simulations %U https://doi.org/10.1534%2Fgenetics.107.085332 %V 178 %X We present an exact forward-in-time algorithm that can efficiently simulate the evolution of a finite population under the Wright–Fisher model. We used simulations based on this algorithm to verify the accuracy of the ancestral recombination graph approximation by comparing it to the exact Wright–Fisher scenario. We find that the recombination graph is generally a very good approximation for models with complete outcrossing, whereas, for models with self-fertilization, the approximation becomes slightly inexact for some combinations of selfing and recombination parameters. COALESCENT theory provides a continuous-time approximation for the history of small samples in large populations and coalescent simulation is a widely used tool in population genetics. Under this framework, the genealogy of a sample of DNA sequences is modeled backward in time and neutral mutations are superposed on this genealogy to generate sequence polymorphism data (Kingman 1982; Hudson 1983; Rosenberg and Nordborg 2002). Forward simulations, in contrast, model the evolution of all the sequences in a population exactly, forward in time and generation by generation. Because coalescent simulations consider only those chromosomes that carry material ancestral to the sample, and, by making a continuous-time approximation skip uninteresting generations whose events do not affect the sample, they are computationally much more efficient than forward simulation programs. However, despite their inefficiency, forward simulations are necessary if we wish to simulate data sets under complex and realistic biological scenarios (e.g., natural selection at multiple linked loci) that are difficult to model accurately using the coalescent. Given the dramatic growth in the power of computing, forward-time simulations are currently feasible for large genomic regions (e.g., megabase scale) and many simulation packages have been developed recently (e.g., Balloux 2001; Hey 2004; Hoggart et al. 2005; Peng and Kimmel 2005; Dudek et al. 2006; Guillaume and Rougemont 2006; Sanford et al. 2007) and have also found important applications (e.g., Balloux and Goudet 2002; Pineda-Krch and Redfield 2005; Peng and Kimmel 2007). Here, we present an exact forward-in-time algorithm that can efficiently simulate the evolution of a finite population undergoing mutations, recombination, and natural selection at multiple linked loci. In contrast to existing forward-time simulators that consider the population genealogy generation by generation, our forward algorithm uses the genealogical information for multiple generations at a time, and on the basis of this information, simulates only those chromosomes in the next generation that can potentially contribute to the future population. We show that such a forward–backward scheme combined with other optimizations can lead to substantial improvements in run-time efficiency. We use our simulation program to evaluate coalescent models with recombination by comparing them to the exact Wright–Fisher model.

@article{Padhukasahasram_2008, abstract = {We present an exact forward-in-time algorithm that can efficiently simulate the evolution of a finite population under the Wright–Fisher model. We used simulations based on this algorithm to verify the accuracy of the ancestral recombination graph approximation by comparing it to the exact Wright–Fisher scenario. We find that the recombination graph is generally a very good approximation for models with complete outcrossing, whereas, for models with self-fertilization, the approximation becomes slightly inexact for some combinations of selfing and recombination parameters. COALESCENT theory provides a continuous-time approximation for the history of small samples in large populations and coalescent simulation is a widely used tool in population genetics. Under this framework, the genealogy of a sample of DNA sequences is modeled backward in time and neutral mutations are superposed on this genealogy to generate sequence polymorphism data (Kingman 1982; Hudson 1983; Rosenberg and Nordborg 2002). Forward simulations, in contrast, model the evolution of all the sequences in a population exactly, forward in time and generation by generation. Because coalescent simulations consider only those chromosomes that carry material ancestral to the sample, and, by making a continuous-time approximation skip uninteresting generations whose events do not affect the sample, they are computationally much more efficient than forward simulation programs. However, despite their inefficiency, forward simulations are necessary if we wish to simulate data sets under complex and realistic biological scenarios (e.g., natural selection at multiple linked loci) that are difficult to model accurately using the coalescent. Given the dramatic growth in the power of computing, forward-time simulations are currently feasible for large genomic regions (e.g., megabase scale) and many simulation packages have been developed recently (e.g., Balloux 2001; Hey 2004; Hoggart et al. 2005; Peng and Kimmel 2005; Dudek et al. 2006; Guillaume and Rougemont 2006; Sanford et al. 2007) and have also found important applications (e.g., Balloux and Goudet 2002; Pineda-Krch and Redfield 2005; Peng and Kimmel 2007). Here, we present an exact forward-in-time algorithm that can efficiently simulate the evolution of a finite population undergoing mutations, recombination, and natural selection at multiple linked loci. In contrast to existing forward-time simulators that consider the population genealogy generation by generation, our forward algorithm uses the genealogical information for multiple generations at a time, and on the basis of this information, simulates only those chromosomes in the next generation that can potentially contribute to the future population. We show that such a forward–backward scheme combined with other optimizations can lead to substantial improvements in run-time efficiency. We use our simulation program to evaluate coalescent models with recombination by comparing them to the exact Wright–Fisher model.}, added-at = {2017-11-16T07:36:30.000+0100}, author = {Padhukasahasram, B. and Marjoram, P. and Wall, J. D. and Bustamante, C. D. and Nordborg, M.}, biburl = {https://www.bibsonomy.org/bibtex/2f02f0c26be9b641f49248b7d07ff69d6/peter.ralph}, doi = {10.1534/genetics.107.085332}, interhash = {6afbf53c43c9b6cfc5c4c9c768082593}, intrahash = {f02f0c26be9b641f49248b7d07ff69d6}, journal = {Genetics}, keywords = {ARG forwards_time methods simulation software}, month = apr, number = 4, pages = {2417--2427}, publisher = {Genetics Society of America}, timestamp = {2017-11-16T07:36:30.000+0100}, title = {Exploring Population Genetic Models With Recombination Using Efficient Forward-Time Simulations}, url = {https://doi.org/10.1534%2Fgenetics.107.085332}, volume = 178, year = 2008 }