GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies.
GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies.
复制标题
DOI：
10.1186/s12864-018-4460-0
复制
发表时间：
2018-05-09
期刊：
影响因子：
4.4
通讯作者：
Mutlu O
中科院分区：
文献类型：
--
作者：
Kim JS;Senol Cali D;Xin H;Lee D;Ghose S;Alser M;Hassan H;Ergin O;Alkan C;Mutlu O
种子位置筛选在DNA读取图谱中是至关重要的，该过程将从供体采集的数十亿个DNA片段(读取)映射到参考基因组上，以识别供体的基因组变体。现有技术的读出映射器1)为每个读出中的种子(即较小片段)快速生成可能的映射位置，2)在每个映射位置提取参考序列，以及3)使用计算昂贵的算法(即，序列比对)检查每个读出与其关联的参考序列之间的相似性，以确定读出的起源。种子位置过滤器在比对之前开始发挥作用，丢弃比对会被认为匹配不佳的种子位置。理想的种子位置过滤器将在比对之前丢弃所有较差的匹配位置，从而不会在不必要的比对上浪费计算。我们提出了一种新的种子位置过滤算法GRIM-Filter，该算法针对3D堆叠存储系统进行了优化，该存储系统将计算集成在堆叠在存储层下的逻辑层中，以执行内存中处理(PIM)。GRIM-Filter通过1)引入参考基因组的粗粒度片段的新表示，以及2)使用大规模并行的内存操作来识别每个粗粒度片段中的读取存在，从而快速过滤种子位置。我们的评估表明，对于0.05%的序列比对误差容忍度，GRIM-Filter 1)将过滤的漏检率降低了5.59x-6.41x，2)提供了1.81x-3.65x的端到端读取映射器加速比，与采用最好的种子位置过滤算法的最先进的读取映射器相比。GRIM-Filter利用3D堆叠内存，从而能够有效地使用内存中的处理，以克服种子位置过滤中的内存带宽瓶颈。我们表明，GRIM-Filter显著提高了最先进的读取映射器的性能。GRIM-Filter是一种通用种子位置过滤器，可应用于任何读取映射器。我们希望我们的结果为设计其他生物信息学算法提供灵感，这些算法利用新兴技术和新的处理范式，例如使用3D堆叠存储设备的内存处理。
Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locations for seeds (i.e., smaller segments) within each read, 2) extract reference sequences at each of the mapping locations, and 3) check similarity between each read and its associated reference sequences with a computationally-expensive algorithm (i.e., sequence alignment) to determine the origin of the read. A seed location filter comes into play before alignment, discarding seed locations that alignment would deem a poor match. The ideal seed location filter would discard all poor match locations prior to alignment such that there is no wasted computation on unnecessary alignments. We propose a novel seed location filtering algorithm, GRIM-Filter, optimized to exploit 3D-stacked memory systems that integrate computation within a logic layer stacked under memory layers, to perform processing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1) introducing a new representation of coarse-grained segments of the reference genome, and 2) using massively-parallel in-memory operations to identify read presence within each coarse-grained segment. Our evaluations show that for a sequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the false negative rate of filtering by 5.59x–6.41x, and 2) provides an end-to-end read mapper speedup of 1.81x–3.65x, compared to a state-of-the-art read mapper employing the best previous seed location filtering algorithm. GRIM-Filter exploits 3D-stacked memory, which enables the efficient use of processing-in-memory, to overcome the memory bandwidth bottleneck in seed location filtering. We show that GRIM-Filter significantly improves the performance of a state-of-the-art read mapper. GRIM-Filter is a universal seed location filter that can be applied to any read mapper. We hope that our results provide inspiration for new works to design other bioinformatics algorithms that take advantage of emerging technologies and new processing paradigms, such as processing-in-memory using 3D-stacked memory devices.
登录
查看更多内容
影响因子：
30.8
作者：
Alkan, Can;Kidd, Jeffrey M.;Marques-Bonet, Tomas;Aksay, Gozde;Antonacci, Francesca;Hormozdiari, Fereydoun;Kitzman, Jacob O.;Baker, Carl;Malig, Maika;Mutlu, Onur;Sahinalp, S. Cenk;Gibbs, Richard A.;Eichler, Evan E.
通讯作者：
Eichler, Evan E.
影响因子：
14.9
作者：
Ahmadi A;Behm A;Honnalli N;Li C;Weng L;Xie X
通讯作者：
Xie X
影响因子：
2
作者：
Aluru, Srinivas;Jammula, Nagakishore
通讯作者：
Jammula, Nagakishore
影响因子：
5.8
作者：
Alser, Mohammed;Hassan, Hasan;Alkan, Can
通讯作者：
Alkan, Can