GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping
GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping
复制标题
DOI：
10.1093/bioinformatics/btx342
复制
发表时间：
2017-11-01
期刊：
影响因子：
5.8
通讯作者：
Alkan, Can
中科院分区：
文献类型：
--
作者：
Alser, Mohammed;Hassan, Hasan;Alkan, Can
动机：高通量DNA测序（HTS）技术会产生过多的小DNA片段（称为短读段），这会导致显著的计算负担。为了分析整个基因组，数十亿个短读段中的每一个都必须基于读段和参考基因组中的“候选”位置之间的相似性映射到参考基因组。被称为比对的相似性测量被公式化为近似字符串匹配问题，是计算瓶颈，因为：（i）其使用二次时间动态编程算法来实现，以及（ii）参考基因组中的大多数候选位置由于高相异度而不与给定读段比对。计算这种不正确的候选位置的对齐消耗了现代读映射器的绝大多数执行时间。因此，它是至关重要的，以开发一个快速，有效的过滤器，可以检测不正确的候选位置，并消除它们之前调用计算成本高昂的对齐algorithm.Results：我们提出了守门员，一个新的硬件加速器，功能作为一个预对齐步骤，快速过滤出最不正确的候选位置。GateKeeper是第一个使用现场可编程门阵列（FPGA）加速预对准的设计，其执行预对准的速度比软件快得多。当在单个FPGA芯片上实现时，GateKeeper保持高精度（平均>96%），同时提供平均90倍和130倍的加速，分别超过最先进的软件预对准技术，邻接滤波器和移位汉明距离（SHD）。添加GateKeeper作为预对齐步骤可以将mrFAST映射器的验证时间减少10倍。
Motivation: High throughput DNA sequencing (HTS) technologies generate an excessive number of small DNA segments - called short reads- that cause significant computational burden. To analyze the entire genome, each of the billions of short reads must be mapped to a reference genome based on the similarity between a read and 'candidate' locations in that reference genome. The similarity measurement, called alignment, formulated as an approximate string matching problem, is the computational bottleneck because: (i) it is implemented using quadratic-time dynamic programming algorithms and (ii) the majority of candidate locations in the reference genome do not align with a given read due to high dissimilarity. Calculating the alignment of such incorrect candidate locations consumes an overwhelming majority of a modern read mapper's execution time. Therefore, it is crucial to develop a fast and effective filter that can detect incorrect candidate locations and eliminate them before invoking computationally costly alignment algorithms.Results: We propose GateKeeper, a new hardware accelerator that functions as a pre-alignment step that quickly filters out most incorrect candidate locations. GateKeeper is the first design to accelerate pre-alignment using Field-Programmable Gate Arrays (FPGAs), which can perform pre-alignment much faster than software. When implemented on a single FPGA chip, GateKeeper maintains high accuracy (on average >96%) while providing, on average, 90-fold and 130-fold speedup over the state-of-the-art software pre-alignment techniques, Adjacency Filter and Shifted Hamming Distance (SHD), respectively. The addition of GateKeeper as a pre-alignment step can reduce the verification time of the mrFAST mapper by a factor of 10.