Efficiently Summarizing Relationships in Large Samples: A General Duality Between Statistics of Genealogies and Genomes

Abstract

As a genetic mutation is passed down across generations, it distinguishes those genomes that have inherited it from those that have not, providing a glimpse of the genealogical tree relating the genomes to each other at that site. Statistical summaries of genetic variation therefore also describe the underlying genealogies. We use this correspondence to define a general framework that efficiently computes single-site population genetic statistics using the succinct tree sequence encoding of genealogies and genome sequence. The general approach accumulates sample weights within the genealogical tree at each position on the genome, which are then combined using a summary function; different statistics result from different choices of weight and function. Results can be reported in three ways: by site, which corresponds to statistics calculated as usual from genome sequence; by branch, which gives the expected value of the dual site statistic under the infinite sites model of mutation, and by node, which summarizes the contribution of each ancestor to these statistics. We use the framework to implement many currently defined statistics of genome sequence (making the statistics’ relationship to the underlying genealogical trees concrete and explicit), as well as the corresponding branch statistics of tree shape. We evaluate computational performance using simulated data, and show that calculating statistics from tree sequences using this general framework is several orders of magnitude more efficient than optimized matrix-based methods in terms of both run time and memory requirements. We also explore how well the duality between site and branch statistics holds in practice on trees inferred from the 1000 Genomes Project data set, and discuss ways in which deviations may encode interesting biological signals.

Shown for reading. Its publisher allows quoting it, not republishing it.

References 72

1. 1.

   Achaz G., 2009 Frequency spectrum neutrality tests: one for all and all for one. Genetics 183: 249–258.

   Not in our library10.1534/genetics.109.104042

2. 2.

   Aguillon S. M., Fitzpatrick J. W., Bowman R., Schoech S. J., Clark A. G., 2017 Deconstructing isolation-by-distance: the genomic consequences of limited dispersal. PLoS Genet. 13: e1006911

   Not in our library10.1371/journal.pgen.1006911

3. 3.

   Ané C., and Sanderson M. J., 2005 Missing the forest for the trees: phylogenetic compression and its implications for inferring complex evolutionary histories. Syst. Biol. 54: 146–157.

   Not in our library10.1080/10635150590905984

4. 4.

   Beaumont M. A., Zhang W., and Balding D. J., 2002 Approximate Bayesian computation in population genetics. Genetics 162: 2025–2026.

   Not in our library10.1093/genetics/162.4.2025

5. 5.

   Becquet C., and Przeworski M., 2007 A new approach to estimate parameters of speciation models with application to apes. Genome Res. 17: 1505–1519.

   Not in our library10.1101/gr.6409707

6. 6.

   Beeravolu C. R., Hickerson M. J., Frantz L. A., and Lohse K., 2018 ABLE: blockwise site frequency spectra for inferring complex population histories and recombination. Genome Biol. 19: 145

   Not in our library10.1186/s13059-018-1517-y

7. 7.

   Booker T. R., and Keightley P. D., 2018 Understanding the factors that shape patterns of nucleotide diversity in the house mouse genome. Mol. Biol. Evol. 35: 2971–2988.

   Not in our library10.1093/molbev/msy188

8. 8.

   Browning S. R., and Browning B. L., 2010 High-resolution detection of identity by descent in unrelated individuals. Am. J. Hum. Genet. 86: 526–539.

   Not in our library10.1016/j.ajhg.2010.02.021

9. 9.

   Browning B. L., Zhou Y., and Browning S. R., 2018 A one-penny imputed genome from next-generation reference panels. Am. J. Hum. Genet. 103: 338–348.

   Not in our library10.1016/j.ajhg.2018.07.015

10. 10.
    The UK Biobank resource with deep phenotyping and genomic data · 2018

    No notice
11. 11.

    Charlesworth B., Nordborg M., and Charlesworth D., 1997 The effects of local selection, balanced polymorphism and background selection on equilibrium patterns of genetic diversity in subdivided populations. Genet. Res. 70: 155–174.

    Not in our library10.1017/s0016672397002954

12. 12.

    Christley S., Lu Y., Li C., and Xie X., 2008 Human genomes as email attachments. Bioinformatics 25: 274–275.

    Not in our library10.1093/bioinformatics/btn582

13. 13.

    Csilléry K., Blum M. G., Gaggiotti O. E., and François O., 2010 Approximate Bayesian computation (ABC) in practice. Trends Ecol. Evol. 25: 410–418.

    Not in our library10.1016/j.tree.2010.04.001

14. 14.

    Danek A., and Deorowicz S., 2018 GTC: how to maintain huge genotype collections in a compressed form. Bioinformatics 34: 1834–1840.

    Not in our library10.1093/bioinformatics/bty023

15. 15.
    Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT) · 2014

    No notice
16. 16.

    Eppstein D., 1994 Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms 17: 237–250.

    Not in our library10.1006/jagm.1994.1033

17. 17.

    Eppstein D., Galil Z., Italiano G. F., and Nissenzweig A., 1997 Sparsification – a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44: 669–696.

    Not in our library10.1145/265910.265914

18. 18.

    Felsenstein J., 2004 Inferring Phylogenies. Sinauer Associates, Sunderland, MA.

    Not in our library

19. 19.

    Ferretti L., Ledda A., Wiehe T., Achaz G., and Ramos-Onsins S. E., 2017 Decomposing the site frequency spectrum: the impact of tree topology on neutrality tests. Genetics 207: 229–240.

    Not in our library10.1534/genetics.116.188763

20. 20.

    Fu Y. X., 1995 Statistical properties of segregating sites. Theor. Popul. Biol. 48: 172–197.

    Not in our library10.1006/tpbi.1995.1025

21. 21.

    Galloway J., Cresko W. A., and Ralph P., 2020 A few stickleback suffice for the transport of alleles to new lakes. G3 (Bethesda) 10: 505–514.

    Not in our library10.1534/g3.119.400564

22. 22.

    1000 Genomes Project Consortium, Auton A., Brooks L. D., Durbin R. M., Garrison E. P., 2015 A global reference for human genetic variation. Nature 526: 68–74.

    Not in our library10.1038/nature15393

23. 23.

    Gillespie J. H., and Langley C. H., 1979 Are evolutionary rates really variable? J. Mol. Evol. 13: 27–34.

    Not in our library10.1007/bf01732751

24. 24.

    Griffiths, R. C., 1991 The two-locus ancestral graph, pp. 100–117 in Lecture Notes-Monograph Series. Ishwar V. Basawa and Robert L. Taylor (Editors). Institute of Mathematical Statistics, Hayward, CA

    Not in our library

25. 25.

    Griffiths R. C., and Marjoram P., 1996 Ancestral inference from samples of DNA sequences with recombination. J. Comput. Biol. 3: 479–502.

    Not in our library10.1089/cmb.1996.3.479

26. 26.

    Haenel Q., Laurentino T. G., Roesti M., and Berner D., 2018 Meta-analysis of chromosome-scale crossover rate variation in eukaryotes and its significance to evolutionary genomics. Mol. Ecol. 27: 2477–2497.

    Not in our library10.1111/mec.14699

27. 27.

    Haller B. C., and Messer P. W., 2019 SLiM 3: forward genetic simulations beyond the Wright–Fisher model. Mol. Biol. Evol. 36: 632–637.

    Not in our library10.1093/molbev/msy228

28. 28.

    Haller B. C., Galloway J., Kelleher J., Messer P. W., and Ralph P. L., 2019 Tree-sequence recording in SLiM opens new horizons for forward-time simulation of whole genomes. Mol. Ecol. Resour 19: 552–566.

    Not in our library10.1111/1755-0998.12968

29. 29.

    Harris K., 2019 From a database of genomes to a forest of evolutionary trees. Nat. Genet. 51: 1306–1307.

    Not in our library10.1038/s41588-019-0492-x

30. 30.

    Holm J., De Lichtenberg K., Thorup M., and Thorup M., 2001 Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. Assoc. Comput. Mach. 48: 723–760.

    Not in our library10.1145/502090.502095

31. 31.

    Hudson R. R., 1983 Properties of a neutral allele model with intragenic recombination. Theor. Popul. Biol. 23: 183–201.

    Not in our library10.1016/0040-5809(83)90013-8

32. 32.

    Hudson R. R., 1994 How can the low levels of DNA sequence variation in regions of the Drosophila genome with low recombination rates be explained? Proc. Natl. Acad. Sci. USA 91: 6815–6818.

    Not in our library10.1073/pnas.91.15.6815

33. 33.

    Hudson R. R., 2001 Two-locus sampling distributions and their application. Genetics 159: 1805–1817.

    Not in our library10.1093/genetics/159.4.1805

34. 34.
    The mutational constraint spectrum quantified from variation in 141,456 humans · 2020

    Corrected
35. 35.
    Efficient Coalescent Simulation and Genealogical Analysis for Large Sample Sizes · 2016

    No notice
36. 36.
    Efficient pedigree recording for fast population genetics simulation · 2018

    No notice
37. 37.

    Kelleher J., Wong Y., Wohns A. W., Fadil C., Albers P. K., 2019 Inferring whole-genome histories in large population datasets. Nat. Genet. 51: 1330–1338 (erratum: Nat. Genet. 51: 1660).

    Not in our library10.1038/s41588-019-0483-y

38. 38.

    Kreitman M., 1983 Nucleotide polymorphism at the alcohol dehydrogenase locus of Drosophila melanogaster. Nature 304: 412–417.

    Not in our library10.1038/304412a0

39. 39.

    Lacki, J., and P. Sankowski, 2013 Reachability in graph timelines, pp. 257–268 in Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, Association for Computing Machinery, New York.

    Not in our library

40. 40.

    Layer R. M., Kindlon N., Karczewski K. J., Quinlan A. R., Consortium E. A., 2016 Efficient genotype compression and analysis of large genetic-variation data sets. Nat. Methods 13: 63–65.

    Not in our library10.1038/nmeth.3654

Cited by papers we hold 1

• Efficient ancestry and mutation simulation with msprime 1.0 · 2021
  No notice

Reads

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.