How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories
© Copyright 2020, Mary Ann Liebert, Inc., publishers 2020. 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 guarante...
| Автори: | , , , , |
|---|---|
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Mary Ann Liebert Inc
2021
|
| Онлайн доступ: | https://hdl.handle.net/1721.1/136639 |
| _version_ | 1826209612095815680 |
|---|---|
| author | Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind |
| author_facet | Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind |
| author_sort | Kim, Younhun |
| collection | MIT |
| description | © Copyright 2020, Mary Ann Liebert, Inc., publishers 2020. 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. |
| first_indexed | 2024-09-23T14:25:13Z |
| format | Article |
| id | mit-1721.1/136639 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:25:13Z |
| publishDate | 2021 |
| publisher | Mary Ann Liebert Inc |
| record_format | dspace |
| spelling | mit-1721.1/1366392021-10-28T03:36:44Z How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind © Copyright 2020, Mary Ann Liebert, Inc., publishers 2020. 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. 2021-10-27T20:36:23Z 2021-10-27T20:36:23Z 2020 2021-05-24T18:39:00Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136639 en 10.1089/CMB.2019.0318 Journal of Computational Biology Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Mary Ann Liebert Inc Mary Ann Liebert |
| spellingShingle | Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title | How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title_full | How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title_fullStr | How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title_full_unstemmed | How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title_short | How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories |
| title_sort | how many subpopulations is too many exponential lower bounds for inferring population histories |
| url | https://hdl.handle.net/1721.1/136639 |
| work_keys_str_mv | AT kimyounhun howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT koehlerfrederic howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT moitraankur howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT mosselelchanan howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT ramnarayangovind howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories |