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

41. 41.
    Revisiting an Old Riddle: What Determines Genetic Diversity Levels within Species? · 2012

    No notice
42. 42.

    Li H., and Wiehe T., 2013 Coalescent tree imbalance and a simple test for selective sweeps based on microsatellite variation. PLOS Comput. Biol. 9: e1003060

    Not in our library10.1371/journal.pcbi.1003060

43. 43.

    Lin M. F., Bai X., Salerno W. J., and Reid J. G., 2019 Sparse project VCF: efficient encoding of population genotype matrices. bioRxiv. (Preprint posted April 17, 2019)

    Not in our library10.1101/611954

44. 44.

    Lohse K., 2017 Come on feel the noise–from metaphors to null models. J. Evol. Biol. 30: 1506–1508.

    Not in our library10.1111/jeb.13109

45. 45.

    Lohse K., Chmelik M., Martin S. H., and Barton N. H., 2016 Efficient strategies for calculating blockwise likelihoods under the coalescent. Genetics 202: 775–786.

    Not in our library10.1534/genetics.115.183814

46. 46.

    Martin A. R., Gignoux C. R., Walters R. K., Wojcik G. L., Neale B. M., 2017 Human demographic history impacts genetic risk prediction across diverse populations. Am. J. Hum. Genet. 100: 635–649.

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

47. 47.

    McVean G. A. T., 2002 A genealogical interpretation of linkage disequilibrium. Genetics 162: 987–991.

    Not in our library10.1093/genetics/162.2.987

48. 48.

    Miles A. and Harding N., 2017 cggh/scikit-allel: v1.1.8 (Version v1.1.8). Zenodo. Available at:

    Not in our library10.5281/zenodo.822784

49. 49.

    Minichiello M. J., and Durbin R., 2006 Mapping trait loci by use of inferred ancestral recombination graphs. Am. J. Hum. Genet. 79: 910–922.

    Not in our library10.1086/508901

50. 50.

    Narasimhan V. M., Rahbari R., Scally A., Wuster A., Mason D., 2017 Estimating the human mutation rate from autozygous segments reveals population differences in human mutational processes. Nat. Commun. 8: 303

    Not in our library10.1038/s41467-017-00323-y

51. 51.

    Patterson N., Moorjani P., Luo Y., Mallick S., Rohland N., 2012 Ancient admixture in human history. Genetics 192: 1065–1093.

    Not in our library10.1534/genetics.112.145037

52. 52.

    Purcell S., Neale B., Todd-Brown K., Thomas L., Ferreira M. A., 2007 Plink: a tool set for whole-genome association and population-based linkage analyses. Am. J. Hum. Genet. 81: 559–575.

    Not in our library10.1086/519795

53. 53.

    Qiao D., Yip W.-K., and Lange C., 2012 Handling the data management needs of high-throughput sequencing data: speedgene, a compression algorithm for the efficient storage of genetic data. BMC Bioinformatics 13: 100

    Not in our library10.1186/1471-2105-13-100

54. 54.

    Ralph P. L., 2019 An empirical approach to demographic inference with genomic data. Theor. Popul. Biol. 127: 91–101.

    Not in our library10.1016/j.tpb.2019.03.005

55. 55.
    Genome-Wide Inference of Ancestral Recombination Graphs · 2014

    No notice
56. 56.

    Reich D., Thangaraj K., Patterson N., Price A. L., and Singh L., 2009 Reconstructing indian population history. Nature 461: 489–494.

    Not in our library10.1038/nature08365

57. 57.

    Sambo F., Di Camillo B., Toffolo G., and Cobelli C., 2014 Compression and fast retrieval of SNP data. Bioinformatics 30: 3078–3085.

    Not in our library10.1093/bioinformatics/btu495

58. 58.

    Scheib C. L., Hui R., D’Atanasio E., Wohns A. W., Inskip S. A., 2019 East Anglian early Neolithic monument burial linked to contemporary Megaliths. Ann. Hum. Biol. 46: 145–149.

    Not in our library10.1080/03014460.2019.1623912

59. 59.
    Supervised Machine Learning for Population Genetics: A New Paradigm · 2018

    No notice
60. 60.

    Semple C., and Steel M. A., 2003 Phylogenetics. Oxford University Press, Oxford.

    Not in our library

61. 61.

    Slatkin M., 1991 Inbreeding coefficients and coalescence times. Genet. Res. 58: 167–175.

    Not in our library10.1017/s0016672300029827

62. 62.

    Speidel L., Forest M., Shi S., and Myers S. R., 2019 A method for genome-wide genealogy estimation for thousands of samples. Nat. Genet. 51: 1321–1329.

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

63. 63.

    Srinivasan S., Pollard S., Das S. K., Norris B., and Bhowmick S., 2018 A shared-memory algorithm for updating tree-based properties of large dynamic networks. IEEE Trans. Big Data.

    Not in our library

64. 64.
    Widespread selection and gene flow shape the genomic landscape during a radiation of monkeyflowers · 2019

    No notice
65. 65.

    Supek F., and Lehner B., 2015 Differential DNA mismatch repair underlies mutation rate variation across the human genome. Nature 521: 81–84.

    Not in our library10.1038/nature14173

66. 66.

    Tajima F., 1983 Evolutionary relationship of DNA sequences in finite populations. Genetics 105: 437–460.

    Not in our library10.1093/genetics/105.2.437

67. 67.

    Tajima F., 1989 Statistical method for testing the neutral mutation hypothesis by DNA polymorphism. Genetics 123: 585–595.

    Not in our library10.1093/genetics/123.3.585

68. 68.

    Tavaré S., 1984 Line-of-descent and genealogical processes, and their applications in population genetics models. Theor. Popul. Biol. 26: 119–164.

    Not in our library10.1016/0040-5809(84)90027-3

69. 69.

    Thornton K. R., 2003 Libsequence: a C++ class library for evolutionary genetic analysis. Bioinformatics 19: 2325–2327.

    Not in our library10.1093/bioinformatics/btg316

70. 70.

    Thornton K. R., 2014 A C++ template library for efficient forward-time population genetic simulation of large populations. Genetics 198: 157–166.

    Not in our library10.1534/genetics.114.165019

71. 71.

    Watterson G. A., 1975 On the number of segregating sites in genetical models without recombination. Theor. Popul. Biol. 7: 256–276.

    Not in our library10.1016/0040-5809(75)90020-9

72. 72.

    Zöllner S., and Pritchard J. K., 2005 Coalescent-based association mapping and fine mapping of complex trait loci. Genetics 169: 1071–1092.

    Not in our library10.1534/genetics.104.031799

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.