How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories
Younhun Kima✉, Frederic Koehlera, Ankur Moitraa b, Elchanan Mossela c, Govind Ramnarayanb
- aDepartment of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts
- bCSAIL, Massachusetts Institute of Technology, Cambridge, Massachusetts
- cDepartment of Mathematics, Institute for Data, Systems and Society, Massachusetts Institute of Technology, Cambridge, Massachusetts
- ✉Corresponding author
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
Reconstruction of population histories is a central problem in population genetics. Existing coalescent-based methods, such as the seminal work of Li and Durbin, 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.
TL;DRThis work proves 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, and essentially determines the optimal number of samples needed to learn an exponential mixture distribution information-theoretically. (Semantic Scholar)