Fulltext

GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping

Alser, Mohammed ; Hassan, Hasan ; Xin, Hongyi ; Ergin, Oğuz ; Mutlu, Onur ; Alkan, Can ; Berger, Bonnie ; Berger, Bonnie

In: Bioinformatics, 2017, vol. 33, no. 21, p. 3355-3363

Ajouter à la liste personnelle
    Titre
    • GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping
    Auteur
    • Alser, Mohammed. Department of Computer Engineering, Bilkent University, Bilkent, Ankara, Turkey
    • Hassan, Hasan. TOBB University of Economics & Technology, Sogutozu, Ankara, Turkey
    • Xin, Hongyi. Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA
    • Ergin, Oğuz. TOBB University of Economics & Technology, Sogutozu, Ankara, Turkey
    • Mutlu, Onur. Department of Computer Science, ETH Zürich, Zürich, Switzerland
    • Alkan, Can. Department of Computer Engineering, Bilkent University, Bilkent, Ankara, Turkey
    • Berger, Bonnie. Department of Computer Engineering, Bilkent University, Bilkent, Ankara, Turkey
    • Berger, Bonnie. Department of Computer Engineering, Bilkent University, Bilkent, Ankara, Turkey
    Type de document
    • Postprint
    Identifiant OAI-PMH
    • oai:doc.rero.ch:333044
    Summary
    Abstract 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. Availability and implementation https://github.com/BilkentCompGen/GateKeeper Supplementary information Supplementary data are available at Bioinformatics online.