A fast adaptive algorithm for computing whole-genome homology maps
A fast adaptive algorithm for computing whole-genome homology maps
复制标题
DOI：
10.1093/bioinformatics/bty597
复制
发表时间：
2018-09-01
期刊：
影响因子：
5.8
通讯作者：
Aluru, Srinivas
中科院分区：
文献类型：
--
作者：
Jain, Chirag;Koren, Sergey;Aluru, Srinivas
动机：全基因组比对是基因组学中的一个重要问题，用于比较不同物种、将草图装配图映射到参考基因组以及识别重复。然而，对于大型植物和动物基因组来说，这项任务仍然是计算和内存密集型的。此外，当前的实用方法对输出比对的特征缺乏任何保证，因此很难针对不同的应用需求进行调整。结果：我们引入了一种计算长DNA序列之间的局部比对边界的近似算法。给定最小对齐长度和身份阈值，我们的算法使用基于 kmer 的统计数据计算所需的对齐边界和身份估计，并对输出灵敏度保持足够的概率保证。此外，为了优先考虑更高的得分对齐间隔，我们开发了一种基于平面扫描的过滤技术，该技术在理论上是最佳的并且实际上是有效的。这些想法的实施产生了快速、准确的组装到基因组和基因组到基因组映射器。结果，我们能够在大约 1 分钟的总执行时间内将错误校正的全基因组 NA12878 人类组装图映射到 hg38 人类参考基因组，并且在多个数据集上的执行率为 97%。最后，我们对人类基因组进行了敏感的自比对，以计算长度 >= 1 Kbp 和 >= 90% 同一性的所有重复。报告的输出实现了良好的召回率，并且覆盖的碱基数量是当前 UCSC 浏览器的片段重复注释的两倍。
Motivation: Whole-genome alignment is an important problem in genomics for comparing different species, mapping draft assemblies to reference genomes and identifying repeats. However, for large plant and animal genomes, this task remains compute and memory intensive. In addition, current practical methods lack any guarantee on the characteristics of output alignments, thus making them hard to tune for different application requirements.Results: We introduce an approximate algorithm for computing local alignment boundaries between long DNA sequences. Given a minimum alignment length and an identity threshold, our algorithm computes the desired alignment boundaries and identity estimates using kmer-based statistics, and maintains sufficient probabilistic guarantees on the output sensitivity. Further, to prioritize higher scoring alignment intervals, we develop a plane-sweep based filtering technique which is theoretically optimal and practically efficient. Implementation of these ideas resulted in a fast and accurate assembly-to-genome and genome-to-genome mapper. As a result, we were able to map an error-corrected whole-genome NA12878 human assembly to the hg38 human reference genome in about 1 min total execution time and 97% on multiple datasets. Finally, we performed a sensitive self-alignment of the human genome to compute all duplications of length >= 1 Kbp and >= 90% identity. The reported output achieves good recall and covers twice the number of bases than the current UCSC browser's segmental duplication annotation.