IDEAS home Printed from https://ideas.repec.org/a/eee/thpobi/v122y2018icp57-66.html
   My bibliography  Save this article

An efficient algorithm for generating the internal branches of a Kingman coalescent

Author

Listed:
  • Reppell, M.
  • Zöllner, S.

Abstract

Coalescent simulations are a widely used approach for simulating sample genealogies, but can become computationally burdensome in large samples. Methods exist to analytically calculate a sample’s expected frequency spectrum without simulating full genealogies. However, statistics that rely on the distribution of the length of internal coalescent branches, such as the probability that two mutations of equal size arose on the same genealogical branch, have previously required full coalescent simulations to estimate. Here, we present a sampling method capable of efficiently generating limited portions of sample genealogies using a series of analytic equations that give probabilities for the number, start, and end of internal branches conditional on the number of final samples they subtend. These equations are independent of the coalescent waiting times and need only be calculated a single time, lending themselves to efficient computation. We compare our method with full coalescent simulations to show the resulting distribution of branch lengths and summary statistics are equivalent, but that for many conditions our method is at least 10 times faster.

Suggested Citation

  • Reppell, M. & Zöllner, S., 2018. "An efficient algorithm for generating the internal branches of a Kingman coalescent," Theoretical Population Biology, Elsevier, vol. 122(C), pages 57-66.
  • Handle: RePEc:eee:thpobi:v:122:y:2018:i:c:p:57-66
    DOI: 10.1016/j.tpb.2017.05.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0040580916301204
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tpb.2017.05.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alex Coventry & Lara M. Bull-Otterson & Xiaoming Liu & Andrew G. Clark & Taylor J. Maxwell & Jacy Crosby & James E. Hixson & Thomas J. Rea & Donna M. Muzny & Lora R. Lewis & David A. Wheeler & Aniko S, 2010. "Deep resequencing reveals excess rare recent variants consistent with explosive population growth," Nature Communications, Nature, vol. 1(1), pages 1-6, December.
    2. Tanya M. Teslovich & Kiran Musunuru & Albert V. Smith & Andrew C. Edmondson & Ioannis M. Stylianou & Masahiro Koseki & James P. Pirruccello & Samuli Ripatti & Daniel I. Chasman & Cristen J. Willer & C, 2010. "Biological, clinical and population relevance of 95 loci for blood lipids," Nature, Nature, vol. 466(7307), pages 707-713, August.
    3. Jewett, Ethan M. & Rosenberg, Noah A., 2014. "Theory and applications of a deterministic approximation to the coalescent model," Theoretical Population Biology, Elsevier, vol. 93(C), pages 14-29.
    4. Jenkins, Paul A. & Song, Yun S., 2011. "The effect of recurrent mutation on the frequency spectrum of a segregating site and the age of an allele," Theoretical Population Biology, Elsevier, vol. 80(2), pages 158-173.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jordi Manuello & Joosung Min & Paul McCarthy & Fidel Alfaro-Almagro & Soojin Lee & Stephen Smith & Lloyd T. Elliott & Anderson M. Winkler & Gwenaëlle Douaud, 2024. "The effects of genetic and modifiable risk factors on brain regions vulnerable to ageing and disease," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    2. Adrienne Tin & Pascal Schlosser & Pamela R. Matias-Garcia & Chris H. L. Thio & Roby Joehanes & Hongbo Liu & Zhi Yu & Antoine Weihs & Anselm Hoppmann & Franziska Grundner-Culemann & Josine L. Min & Vic, 2021. "Epigenome-wide association study of serum urate reveals insights into urate co-regulation and the SLC2A9 locus," Nature Communications, Nature, vol. 12(1), pages 1-18, December.
    3. Ralph, Peter L., 2019. "An empirical approach to demographic inference with genomic data," Theoretical Population Biology, Elsevier, vol. 127(C), pages 91-101.
    4. Maria Mirabelli & Eusebio Chiefari & Patrizia Caroleo & Biagio Arcidiacono & Domenica Maria Corigliano & Stefania Giuliano & Francesco Saverio Brunetti & Sinan Tanyolaç & Daniela Patrizia Foti & Luigi, 2019. "Long-Term Effectiveness of Liraglutide for Weight Management and Glycemic Control in Type 2 Diabetes," IJERPH, MDPI, vol. 17(1), pages 1-11, December.
    5. Sonali Pechlivanis & Susanne Moebus & Nils Lehmann & Raimund Erbel & Amir A Mahabadi & Per Hoffmann & Karl-Heinz Jöckel & Markus M Nöthen & Hagen S Bachmann & on behalf of the Heinz Nixdorf Recall Stu, 2020. "Genetic risk scores for coronary artery disease and its traditional risk factors: Their role in the progression of coronary artery calcification—Results of the Heinz Nixdorf Recall study," PLOS ONE, Public Library of Science, vol. 15(5), pages 1-18, May.
    6. Ferretti, Luca & Klassmann, Alexander & Raineri, Emanuele & Ramos-Onsins, Sebastián E. & Wiehe, Thomas & Achaz, Guillaume, 2018. "The neutral frequency spectrum of linked sites," Theoretical Population Biology, Elsevier, vol. 123(C), pages 70-79.
    7. Linda Ottensmann & Rubina Tabassum & Sanni E. Ruotsalainen & Mathias J. Gerl & Christian Klose & Elisabeth Widén & Kai Simons & Samuli Ripatti & Matti Pirinen, 2023. "Genome-wide association analysis of plasma lipidome identifies 495 genetic associations," Nature Communications, Nature, vol. 14(1), pages 1-15, December.
    8. Mathias I. Nielsen & Noortje Haan & Weston Kightlinger & Zilu Ye & Sally Dabelsteen & Minyan Li & Michael C. Jewett & Ieva Bagdonaite & Sergey Y. Vakhrushev & Hans H. Wandall, 2022. "Global mapping of GalNAc-T isoform-specificities and O-glycosylation site-occupancy in a tissue-forming human cell line," Nature Communications, Nature, vol. 13(1), pages 1-17, December.
    9. Peter H. Dixon & Adam P. Levine & Inês Cebola & Melanie M. Y. Chan & Aliya S. Amin & Anshul Aich & Monika Mozere & Hannah Maude & Alice L. Mitchell & Jun Zhang & Jenny Chambers & Argyro Syngelaki & Je, 2022. "GWAS meta-analysis of intrahepatic cholestasis of pregnancy implicates multiple hepatic genes and regulatory elements," Nature Communications, Nature, vol. 13(1), pages 1-18, December.
    10. Yang, Chiao-Yu & Lei, Lihua & Ho, Nhat & Fithian, William, 2022. "BONuS: Multiple Multivariate Testing with a Data-Adaptive Test Statistic," Research Papers 4031, Stanford University, Graduate School of Business.
    11. Klassmann, A. & Ferretti, L., 2018. "The third moments of the site frequency spectrum," Theoretical Population Biology, Elsevier, vol. 120(C), pages 16-28.
    12. Jiacheng Miao & Hanmin Guo & Gefei Song & Zijie Zhao & Lin Hou & Qiongshi Lu, 2023. "Quantifying portable genetic effects and improving cross-ancestry genetic prediction with GWAS summary statistics," Nature Communications, Nature, vol. 14(1), pages 1-13, December.
    13. Hayman, Elizabeth & Ignatieva, Anastasia & Hein, Jotun, 2023. "Recoverability of ancestral recombination graph topologies," Theoretical Population Biology, Elsevier, vol. 154(C), pages 27-39.
    14. Yordi J. Vegte & Ruben N. Eppinga & M. Yldau Ende & Yanick P. Hagemeijer & Yuvaraj Mahendran & Elias Salfati & Albert V. Smith & Vanessa Y. Tan & Dan E. Arking & Ioanna Ntalla & Emil V. Appel & Claudi, 2023. "Genetic insights into resting heart rate and its role in cardiovascular disease," Nature Communications, Nature, vol. 14(1), pages 1-21, December.
    15. Mike Thompson & Mary Grace Gordon & Andrew Lu & Anchit Tandon & Eran Halperin & Alexander Gusev & Chun Jimmie Ye & Brunilda Balliu & Noah Zaitlen, 2022. "Multi-context genetic modeling of transcriptional regulation resolves novel disease loci," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    16. Xinyuan Zhang & Anastasia M. Lucas & Yogasudha Veturi & Theodore G. Drivas & William P. Bone & Anurag Verma & Wendy K. Chung & David Crosslin & Joshua C. Denny & Scott Hebbring & Gail P. Jarvik & Ifti, 2022. "Large-scale genomic analyses reveal insights into pleiotropy across circulatory system diseases and nervous system disorders," Nature Communications, Nature, vol. 13(1), pages 1-12, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:thpobi:v:122:y:2018:i:c:p:57-66. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/intelligence .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.