How many subpopulations is too many? Exponential lower bounds for inferring population histories

DOI10.1007/978-3-030-17083-7_9MaRDI QIDQ2415258zbMATH OpenOpenAlexFDO

Authors Younhun Kim, Frederic Koehler, Ankur Moitra, Elchanan Mossel, Govind Ramnarayan

Publication date 21 May 2019

Full work available at URL https://arxiv.org/abs/1811.03177, https://hdl.handle.net/1721.1/126860

zbMATH Keywords

mixtures of exponentialspopulation size historiessample complexity

Mathematics Subject Classification ID

Genetics and epigenetics (92D10)

Abstract: Reconstruction of population histories is a central problem in population genetics. Existing coalescent-based methods, like the seminal work of Li and Durbin (Nature, 2011), attempt to solve this problem using sequence data but have no rigorous guarantees. Determining the amount of data needed to correctly reconstruct population histories is a major challenge. Using a variety of tools from information theory, the theory of extremal polynomials, and approximation theory, we prove new sharp information-theoretic lower bounds on the problem of reconstructing population structure -- the history of multiple subpopulations that merge, split and change sizes over time. Our lower bounds are exponential in the number of subpopulations, even when reconstructing recent histories. We demonstrate the sharpness of our lower bounds by providing algorithms for distinguishing and learning population histories with matching dependence on the number of subpopulations. Along the way and of independent interest, we essentially determine the optimal number of samples needed to learn an exponential mixture distribution information-theoretically, proving the upper bound by analyzing natural (and efficient) algorithms for this problem.

Recommendations

• Can one hear the shape of a population history?
• Exact limits of inference in coalescent models
• Inferring population history from genealogical trees
• Sparse moments of univariate step functions and allele frequency spectra
• scientific article; zbMATH DE number 5311824

Cited in

(2)

• On the decidability of population size histories from finite allele frequency spectra
• Can one hear the shape of a population history?

This page was built for publication: How many subpopulations is too many? Exponential lower bounds for inferring population histories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415258)