Genome-wide inference of ancestral recombination graphs

PLoS Genetics
Matthew D RasmussenAdam Siepel

Abstract

The complex correlation structure of a collection of orthologous DNA sequences is uniquely captured by the "ancestral recombination graph" (ARG), a complete record of coalescence and recombination events in the history of the sample. However, existing methods for ARG inference are computationally intensive, highly approximate, or limited to small numbers of sequences, and, as a consequence, explicit ARG inference is rarely used in applied population genomics. Here, we introduce a new algorithm for ARG inference that is efficient enough to apply to dozens of complete mammalian genomes. The key idea of our approach is to sample an ARG of [Formula: see text] chromosomes conditional on an ARG of [Formula: see text] chromosomes, an operation we call "threading." Using techniques based on hidden Markov models, we can perform this threading operation exactly, up to the assumptions of the sequentially Markov coalescent and a discretization of time. An extension allows for threading of subtrees instead of individual sequences. Repeated application of these threading operations results in highly efficient Markov chain Monte Carlo samplers for ARGs. We have implemented these methods in a computer program called ARGweaver. Experiments with...Continue Reading

References

Feb 4, 2014·Theoretical Population Biology·Asger Hobolth, Jens Ledet Jensen
Sep 25, 2014·Annual Review of Genetics·Thomas MailundMikkel Heide Schierup
Feb 18, 2016·Nature·Martin KuhlwilmSergi Castellano
Jan 26, 2016·Nature Genetics·Virginia SavovaAlexander A Gimelbrant
Feb 15, 2016·Trends in Genetics : TIG·Yaniv Brandvain, Stephen I Wright
Jun 10, 2015·Proceedings of the National Academy of Sciences of the United States of America·Jonathan Terhorst, Yun S Song
Mar 4, 2015·Proceedings of the National Academy of Sciences of the United States of America·Kelley Harris
Apr 7, 2015·Epidemics·Simon D W FrostTrevor Bedford
Nov 19, 2014·Evolution; International Journal of Organic Evolution·Ziyue GaoGuy Sella
Feb 3, 2016·Molecular Biology and Evolution·Cesare de FilippoAida M Andrés
May 7, 2015·Molecular Ecology·Anna Fijarczyk, Wiesław Babik
Nov 11, 2015·Nature Reviews. Genetics·Joshua G Schraiber, Joshua M Akey
Jun 21, 2015·Molecular Biology and Evolution·Haley Hunter-Zinck, Andrew G Clark
Apr 7, 2015·Journal of Molecular Evolution·Mary K Kuhner, Jon Yamato
Apr 8, 2015·PLoS Computational Biology·Fabio Pardi, Celine Scornavacca
Aug 18, 2016·PLoS Computational Biology·Pablo G CámaraRaúl Rabadán
Mar 16, 2016·PLoS Genetics·Daniel R Schrider, Andrew D Kern
Oct 6, 2017·Molecular Biology and Evolution·Katherine M Siewert, Benjamin F Voight
Mar 22, 2018·Bioinformatics·R A Leo ElworthLuay Nakhleh
Aug 2, 2017·PLoS Computational Biology·Philippe GambetteCeline Scornavacca
Jan 4, 2019·Proceedings. Mathematical, Physical, and Engineering Sciences·K HeineM De Iorio
Dec 31, 2015·Genetics·Konrad LohseNicholas H Barton
Feb 21, 2019·Molecular Biology and Evolution·Flora JayFrédéric Austerlitz
May 1, 2019·Nature Ecology & Evolution·Martin KuhlwilmTomas Marques-Bonet
Nov 6, 2018·Genetics·Michael D Edge, Graham Coop
Jan 31, 2016·Molecular Ecology·Nathan K SchaeferRichard E Green
Sep 4, 2019·Nature Genetics·Kelley Harris
Sep 4, 2019·Nature Genetics·Jerome KelleherGil McVean
Sep 11, 2019·Systematic Biology·Anton SuvorovDaniel R Schrider
Oct 30, 2016·Science·Marc de ManuelTomas Marques-Bonet
Mar 10, 2020·PLoS Genetics·Iain Mathieson, Aylwyn Scally
Mar 19, 2020·Genome Biology and Evolution·Nilson Da Rocha CoimbraAïda Ouangraoua
Aug 1, 2015·Genetics·Julia A PalaciosSohini Ramachandran
Nov 9, 2016·Genome Biology·Lluis Quintana-Murci
Jun 30, 2019·Science Advances·Tomochika FujisawaTeiji Sota

Citations

Sep 1, 1978·Science·P MenozziL Cavalli-Sforza
Jan 1, 1990·Bulletin of Mathematical Biology·S Wright
Feb 1, 1974·Genetical Research·J M Smith, J Haigh
Apr 1, 1974·Genetical Research·T Maruyama
Dec 1, 1966·Genetical Research·William G Hill, A Robertson
Apr 1, 1983·Theoretical Population Biology·Richard R Hudson
Jan 1, 1981·Journal of Molecular Evolution·J Felsenstein
Apr 1, 1996·Genetical Research·M NordborgD Charlesworth
Jan 1, 1996·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·R C Griffiths, P Marjoram
Jan 1, 1997·Critical Reviews in Immunology·V ApaniusW K Potts
Apr 1, 1998·Bioinformatics·J ZhuC E Lawrence
Feb 3, 1999·Annual Review of Genetics·A L Hughes, M Yeager
Jun 15, 1999·Theoretical Population Biology·C Wiuf, Jotun Hein
May 8, 2001·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·L WangL Zhang
Jun 19, 2001·American Journal of Human Genetics·B Rannala, J P Reeve
Sep 26, 2001·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·D Husmeier, F Wright
Jun 8, 2002·Nature Genetics·Augustine KongKari Stefansson
Aug 9, 2002·Theoretical Population Biology·Fabrice LarribeNicholas J Schork
Oct 10, 2003·Bioinformatics·Simon L Cawley, Lior Pachter
Nov 25, 2003·Nature Reviews. Genetics·Michael P H Stumpf, Gil McVean
Sep 3, 2004·Genetics·Naoki TakebayashiMarcy K Uyenoyama
Oct 19, 2004·Genetics·Sebastian Zöllner, Jonathan K Pritchard
Feb 9, 2005·American Journal of Human Genetics·Matthew Stephens, Paul Scheet
Mar 16, 2005·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Yun S Song, Jotun Hein
Jul 29, 2005·Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences·Gil McVean, Niall J Cardin
Oct 29, 2005·Nature·International HapMap Consortium
Dec 15, 2005·Proceedings of the National Academy of Sciences of the United States of America·Benjamin F VoightAnna Di Rienzo
Feb 24, 2006·PLoS Biology·Benjamin F VoightJonathan K Pritchard
Mar 17, 2006·BMC Genetics·Paul Marjoram, Jeff D Wall
Jun 15, 2006·American Journal of Human Genetics·Hua TangNeil Risch
Oct 13, 2006·American Journal of Human Genetics·Mark J Minichiello, Richard Durbin
Mar 21, 2007·Computational Systems Bioinformatics·Yufeng Wu, Dan Gusfield
Jun 19, 2007·Nature Genetics·Jonathan MarchiniPeter Donnelly

Related Concepts

Computer Software
In Silico
IK gene
GYPE gene
Pyotraumatic Dermatitis
Abnormal Degeneration
Glycophorin A
Methionine synthase reductase
Heuristics
CRHR1 gene

Related Feeds

Birth Defects

Birth defects encompass structural and functional alterations that occur during embryonic or fetal development and are present since birth. The cause may be genetic, environmental or unknown and can result in physical and/or mental impairment. Here is the latest research on birth defects.