Chapter title |
Decoding coalescent hidden Markov models in linear time.
|
---|---|
Chapter number | 8 |
Book title |
Research in Computational Molecular Biology
|
Published in |
Res Comput Mol Biol, October 2014
|
DOI | 10.1007/978-3-319-05269-4_8 |
Pubmed ID | |
Book ISBNs |
978-3-31-905268-7, 978-3-31-905269-4
|
Authors |
Harris K, Sheehan S, Kamm JA, Song YS, Kelley Harris, Sara Sheehan, John A. Kamm, Yun S. Song, Harris, Kelley, Sheehan, Sara, Kamm, John A., Song, Yun S. |
Abstract |
In many areas of computational biology, hidden Markov models (HMMs) have been used to model local genomic features. In particular, coalescent HMMs have been used to infer ancient population sizes, migration rates, divergence times, and other parameters such as mutation and recombination rates. As more loci, sequences, and hidden states are added to the model, however, the runtime of coalescent HMMs can quickly become prohibitive. Here we present a new algorithm for reducing the runtime of coalescent HMMs from quadratic in the number of hidden time states to linear, without making any additional approximations. Our algorithm can be incorporated into various coalescent HMMs, including the popular method PSMC for inferring variable effective population sizes. Here we implement this algorithm to speed up our demographic inference method diCal, which is equivalent to PSMC when applied to a sample of two haplotypes. We demonstrate that the linear-time method can reconstruct a population size change history more accurately than the quadratic-time method, given similar computation resources. We also apply the method to data from the 1000 Genomes project, inferring a high-resolution history of size changes in the European population. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 1 | 100% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 1 | 100% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
United Kingdom | 2 | 6% |
Brazil | 2 | 6% |
France | 1 | 3% |
China | 1 | 3% |
United States | 1 | 3% |
Unknown | 24 | 77% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Student > Ph. D. Student | 11 | 35% |
Researcher | 10 | 32% |
Lecturer | 2 | 6% |
Student > Doctoral Student | 2 | 6% |
Professor | 2 | 6% |
Other | 3 | 10% |
Unknown | 1 | 3% |
Readers by discipline | Count | As % |
---|---|---|
Agricultural and Biological Sciences | 17 | 55% |
Computer Science | 4 | 13% |
Mathematics | 3 | 10% |
Biochemistry, Genetics and Molecular Biology | 2 | 6% |
Unspecified | 1 | 3% |
Other | 2 | 6% |
Unknown | 2 | 6% |