Validating Paired-end Read Alignments in Sequence Graphs-猫眼课题宝

DOI：

10.1101/682799

发表时间：

2019-06

期刊：

bioRxiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Chirag Jain;Haowen Zhang;A. Dilthey;S. Aluru

基于图的非线性参考结构，如变异图和有色de Bruijn图，能够将全部基因组多样性合并到种群中。然而，从简单的基于字符串的引用过渡到图需要解决许多计算挑战，其中之一涉及准确地将排序读取集映射到图。配对末端Illumina测序是基因组学中常用的测序平台，其中配对末端距离限制允许消除重复序列的歧义。许多最近的工作探索了将单个读数映射到图表的基于索引和基于比对的良好策略。然而，有效地验证图上的距离约束并不是一件容易的事情，并且现有的序列到图映射器依赖于启发式算法。我们引入了该问题的数学描述，并给出了一个精确求解该问题的新算法。利用参考图的高度稀疏性，利用稀疏矩阵-矩阵乘法(SpGEMM)建立索引，并通过映射算法对索引进行高效查询以验证距离约束。使用真实的参考图，包括人类MHC变异图和使用20株炭疽杆菌基因组构建的泛基因组de-Bruijn图，验证了算法的有效性。虽然使用我们的算法，一次性索引时间可能从几分钟到几个小时不等，但回答一百万个距离查询只需不到一秒钟。2012年计算→路径和连通性问题的学科分类数学；应用计算→计算基因组学

Graph based non-linear reference structures such as variation graphs and colored de Bruijn graphs enable incorporation of full genomic diversity within a population. However, transitioning from a simple string-based reference to graphs requires addressing many computational challenges, one of which concerns accurately mapping sequencing read sets to graphs. Paired-end Illumina sequencing is a commonly used sequencing platform in genomics, where the paired-end distance constraints allow disambiguation of repeats. Many recent works have explored provably good index-based and alignment-based strategies for mapping individual reads to graphs. However, validating distance constraints efficiently over graphs is not trivial, and existing sequence to graph mappers rely on heuristics. We introduce a mathematical formulation of the problem, and provide a new algorithm to solve it exactly. We take advantage of the high sparsity of reference graphs, and use sparse matrix-matrix multiplications (SpGEMM) to build an index which can be queried efficiently by a mapping algorithm for validating the distance constraints. Effectiveness of the algorithm is demonstrated using real reference graphs, including a human MHC variation graph, and a pan-genome de-Bruijn graph built using genomes of 20 B. anthracis strains. While the one-time indexing time can vary from a few minutes to a few hours using our algorithm, answering a million distance queries takes less than a second. 2012 ACM Subject Classification Mathematics of computing → Paths and connectivity problems; Applied computing → Computational genomics

Validating Paired-end Read Alignments in Sequence Graphs

文献摘要

相似文献