How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories
How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories
复制标题
有多少亚群就太多了？
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Govind Ramnarayan
中科院分区：
文献类型：
--
作者：
Younhun Kim;Frederic Koehler;Ankur Moitra;Elchanan Mossel;Govind Ramnarayan
种群历史的重建是种群遗传学的核心问题。现有的基于凝聚的方法，如Li和Durbin的开创性工作，试图使用序列数据来解决这个问题，但没有严格的保证。确定正确重建人口历史所需的数据量是一项重大挑战。利用信息论、极值多项式理论和近似理论的各种工具，我们证明了重建种群结构问题的新的尖锐的信息论下界-多个亚种群合并、分裂和随时间变化大小的历史。即使在重建最近的历史时，我们的下限在亚种群的数量上也是指数级的。我们通过提供算法来区分和学习具有匹配依赖于子种群数量的种群历史，从而证明了下界的清晰度。在此过程中，我们从理论上确定了学习指数混合分布信息所需的最佳样本数量，并通过分析该问题的自然（和有效）算法证明了上限。
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.