Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/1150
Title: GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping
Authors: Alser, Mohammed
Hassan, Hasan
Xin, Hongyi
Ergin, Oğuz
Mutlu, Onur
Alkan, Can
143001
Keywords: Genome
Exome
read mapping
Issue Date: 1-Nov-2017
Publisher: Oxford Univ Press
Source: Alser, M., Hassan, H., Xin, H., Ergin, O., Mutlu, O., & Alkan, C. (2017). GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping. Bioinformatics, 33(21), 3355-3363.
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.
URI: https://academic.oup.com/bioinformatics/article/33/21/3355/3859176
https://hdl.handle.net/20.500.11851/1150
ISSN: 1367-4803
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
PubMed İndeksli Yayınlar Koleksiyonu / PubMed Indexed Publications Collection
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record

CORE Recommender

SCOPUSTM   
Citations

35
checked on Sep 23, 2022

WEB OF SCIENCETM
Citations

40
checked on Sep 24, 2022

Page view(s)

120
checked on Dec 26, 2022

Google ScholarTM

Check

Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.