How Many Subpopulations Is Too Many?: Exponential Lower Bounds for Inferring Population Histories
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 co...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Springer International Publishing
2020
|
| Online Access: | https://hdl.handle.net/1721.1/126860 |
| _version_ | 1826211417101959168 |
|---|---|
| author | Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind |
| author_sort | Kim, Younhun |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:05:34Z |
| format | Book |
| id | mit-1721.1/126860 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:05:34Z |
| publishDate | 2020 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1268602022-10-02T00:32:22Z How Many Subpopulations Is Too Many?: Exponential Lower Bounds for Inferring Population Histories Kim, Younhun Koehler, Frederic Moitra, Ankur Mossel, Elchanan Ramnarayan, Govind Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Institute for Data, Systems, and Society 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. Office of Naval Research MURI (N00014-16-1-2227) National Science Foundation (Grants CCF1665252, DMS-1737944 and CCF-1565235; Award CCF-1453261) 2020-08-31T23:39:41Z 2020-08-31T23:39:41Z 2019-04 2019-11-15T18:10:59Z Book http://purl.org/eprint/type/ConferencePaper 9783030170820 9783030170837 0302-9743 1611-3349 https://hdl.handle.net/1721.1/126860 Kim, Younhun et al. "How Many Subpopulations Is Too Many?: Exponential Lower Bounds for Inferring Population Histories." International Conference on Research in Computational Molecular Biology, May 2019, Padua Italy, Springer International Publishing, April 2019. © 2019 Springer Nature en http://dx.doi.org/10.1007/978-3-030-17083-7_9 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing arXiv |
| 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/126860 |
| work_keys_str_mv | AT kimyounhun howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT koehlerfrederic howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT moitraankur howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT mosselelchanan howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories AT ramnarayangovind howmanysubpopulationsistoomanyexponentiallowerboundsforinferringpopulationhistories |