# GateKeeper: A New Hardware Architecture for Accelerating Pre-Alignment in DNA Short Read Mapping

arXiv: https://arxiv.org/abs/1604.01789 · HTML: https://mlsanity.com/paper/1604.01789/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2016.

## Built on by (most cited first, 4 of 4)

- [ApHMM: Accelerating Profile Hidden Markov Models for Fast and Energy-Efficient Genome Analysis](https://mlsanity.com/paper/2207.09765/) (2022)
- [EcoFlow: Efficient Convolutional Dataflows for Low-Power Neural Network Accelerators](https://mlsanity.com/paper/2202.02310/) (2022)
- [LEAPER: Fast and Accurate FPGA-based System Performance Prediction via Transfer Learning](https://mlsanity.com/paper/2208.10606/) (2022)
- [Harmonia: Enhancing Data Placement and Migration in Hybrid Storage Systems via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.20507/) (2025)

## Abstract (arXiv)

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: (1) it is implemented using quadratic-time dynamic programming algorithms, and (2) 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 operations. 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. GateKeeper can be integrated with any mapper that performs sequence alignment for verification. When implemented on a single FPGA chip, GateKeeper maintains high accuracy (on average >96%) while providing up to 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: https://github.com/BilkentCompGen/GateKeeper