Large scale sequence alignment via efficient inference in generative models.
Large scale sequence alignment via efficient inference in generative models.
复制标题
DOI：
10.1038/s41598-023-34257-x
复制
发表时间：
2023-05-04
影响因子：
4.6
通讯作者：
中科院分区：
文献类型：
--
作者：
在计算生物学中，找到数百万个读段和基因组序列之间的比对至关重要。由于标准的比对算法具有很大的计算成本，因此已经开发了算法来加速该任务。尽管快了几个数量级，但这些方法缺乏理论保证并且通常具有低灵敏度，特别是当读段相对于基因组具有许多插入、缺失和错配时。在这里，我们开发了一个理论上有原则的和有效的算法，在广泛的插入，删除和突变率具有高灵敏度。我们框架序列比对作为一个概率模型中的推理问题。给定读数和查询读数的参考数据库，我们找到最大化从概率模型与独立模型联合生成的参考读数和查询读数的对数似然比的匹配。这个问题的暴力解决方案计算每个查询和引用对之间的联合和独立概率，其复杂性随数据库大小线性增长。我们引入了一种桶策略，其中具有较高对数似然比的读段以高概率映射到同一桶。实验结果表明，我们的方法是更准确的比对从太平洋生物科学测序仪的基因组序列的长读段比国家的最先进的方法。
Finding alignments between millions of reads and genome sequences is crucial in computational biology. Since the standard alignment algorithm has a large computational cost, heuristics have been developed to speed up this task. Though orders of magnitude faster, these methods lack theoretical guarantees and often have low sensitivity especially when reads have many insertions, deletions, and mismatches relative to the genome. Here we develop a theoretically principled and efficient algorithm that has high sensitivity across a wide range of insertion, deletion, and mutation rates. We frame sequence alignment as an inference problem in a probabilistic model. Given a reference database of reads and a query read, we find the match that maximizes a log-likelihood ratio of a reference read and query read being generated jointly from a probabilistic model versus independent models. The brute force solution to this problem computes joint and independent probabilities between each query and reference pair, and its complexity grows linearly with database size. We introduce a bucketing strategy where reads with higher log-likelihood ratio are mapped to the same bucket with high probability. Experimental results show that our method is more accurate than the state-of-the-art approaches in aligning long-reads from Pacific Bioscience sequencers to genome sequences.
登录
查看更多内容
影响因子：
3
作者：
Slater GS;Birney E
通讯作者：
Birney E
影响因子：
--
作者：
Schuster-Bockler, Benjamin;Bateman, Alex
通讯作者：
Bateman, Alex
影响因子：
5.8
作者：
Li, Heng
通讯作者：
Li, Heng
影响因子：
5.8
作者：
Jain, Chirag;Rhie, Arang;Phillippy, Adam M.
通讯作者：
Phillippy, Adam M.
影响因子：
46.9
作者：
Berlin, Konstantin;Koren, Sergey;Phillippy, Adam M.
通讯作者：
Phillippy, Adam M.