GateKeeper

GateKeeper accelerates pre-alignment filtering of DNA short reads to detect and eliminate incorrect candidate mapping locations before computationally expensive alignment to a reference genome.

Key Features:

• Pre-alignment filtering: Identifies and eliminates incorrect candidate locations prior to sequence alignment to reduce unnecessary verification work.
• Hardware acceleration: Implements the pre-alignment filter on Field-Programmable Gate Arrays (FPGAs) for rapid execution.
• Accuracy: Achieves an average accuracy exceeding 96% when implemented on a single FPGA chip.
• Speedups versus software methods: Provides a 90-fold speedup compared to the Adjacency Filter and a 130-fold speedup relative to the Shifted Hamming Distance (SHD) method.
• Reduction of alignment workload: Decreases the number of candidate locations requiring quadratic-time dynamic programming alignment algorithms.
• Impact on mappers: Reduces verification time for read mappers such as mrFAST by an order of magnitude.

Scientific Applications:

• Short read mapping pre-processing: Filtering candidate mapping locations for DNA short reads from high-throughput sequencing (HTS) prior to alignment.
• Acceleration of read mappers: Decreasing verification time in mappers such as mrFAST to speed overall mapping workflows.
• Scaling large-scale genomic analyses: Reducing computational burden of alignment stages in HTS-based studies by removing unlikely candidate locations.

Methodology:

GateKeeper is implemented on FPGAs to perform hardware-accelerated pre-alignment filtering by detecting and eliminating incorrect candidate locations before invoking quadratic-time dynamic programming alignment algorithms; it was benchmarked against the Adjacency Filter and Shifted Hamming Distance (SHD), reporting >96% accuracy on a single FPGA and 90x and 130x speedups respectively, with an order-of-magnitude reduction in verification time for mrFAST.