Decoding coalescent hidden Markov models in linear time.
Decoding coalescent hidden Markov models in linear time.
复制标题
DOI：
10.1007/978-3-319-05269-4_8
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
在计算生物学的许多领域，隐马尔可夫模型（hmm）已被用于模拟局部基因组特征。特别是，聚结hmm已被用于推断古代种群规模、迁移率、分化时间和其他参数，如突变和重组率。然而，随着更多的基因座、序列和隐藏状态被添加到模型中，聚合hmm的运行时间很快就会变得令人望而却步。在此，我们提出了一种新的算法，在不做任何额外近似的情况下，将合并hmm的运行时间从隐藏时间状态数量的二次型减少到线性型。我们的算法可以应用到各种聚结hmm中，包括常用的PSMC方法来推断可变有效种群大小。在这里，我们实现了这个算法来加速我们的人口统计推断方法dicc，当应用于两个单倍型的样本时，它相当于PSMC。结果表明，在计算资源相似的情况下，线性时间方法比二次时间方法能更准确地重建种群规模变化历史。我们还将该方法应用于1000基因组计划的数据，推断出欧洲人口规模变化的高分辨率历史。
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.