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

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: (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

References in corpus (1)

• Optimal Seed Solver: Optimizing Seed Selection in Read Mapping

Cited by in corpus (21)

• Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions
• Technology dictates algorithms: Recent developments in read alignment
• GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies
• Shouji: A Fast and Efficient Pre-Alignment Filter for Sequence Alignment
• Accelerating Genome Analysis: A Primer on an Ongoing Journey
• FPGA-Based Near-Memory Acceleration of Modern Data-Intensive Applications
• Apollo: A Sequencing-Technology-Independent, Scalable, and Accurate Assembly Polishing Algorithm
• SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
• ASAP: Accelerated Short-Read Alignment on Programmable Hardware
• SeGraM: A Universal Hardware Accelerator for Genomic Sequence-to-Graph and Sequence-to-Sequence Mapping
• GRIM-filter: fast seed filtering in read mapping using emerging memory technologies
• FiltPIM: In-Memory Filter for DNA Sequencing
• GateKeeper-GPU: Fast and Accurate Pre-Alignment Filtering in Short Read Mapping
• MARS: Processing-In-Memory Acceleration of Raw Signal Genome Analysis Inside the Storage Subsystem
• RASSA: Resistive Pre-Alignment Accelerator for Approximate DNA Long Read Mapping
• Enabling Practical Processing in and near Memory for Data-Intensive Computing
• A Workload and Programming Ease Driven Perspective of Processing-in-Memory
• Processing Data Where It Makes Sense: Enabling In-Memory Computation
• DNA Sequence Alignment by Window based Optical Correlator
• Accelerating Genome Sequence Analysis via Efficient Hardware/Algorithm Co-Design
• Accelerating the Understanding of Life's Code Through Better Algorithms and Hardware Design