# GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2020.

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

- [Accelerating Neural Network Inference with Processing-in-DRAM: From the Edge to the Cloud](https://mlsanity.com/paper/2209.08938/) (2022)
- [PIM-Opt: Demystifying Distributed Optimization Algorithms on a Real-World Processing-In-Memory System](https://mlsanity.com/paper/2404.07164/) (2024)
- [An Experimental Evaluation of Machine Learning Training on a Real Processing-in-Memory System](https://mlsanity.com/paper/2207.07886/) (2022)
- [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)
- [Heterogeneous Data-Centric Architectures for Modern Data-Intensive Applications: Case Studies in Machine Learning and Databases](https://mlsanity.com/paper/2205.14664/) (2022)
- [TransPimLib: A Library for Efficient Transcendental Functions on Processing-in-Memory Systems](https://mlsanity.com/paper/2304.01951/) (2023)
- [Harmonia: Enhancing Data Placement and Migration in Hybrid Storage Systems via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.20507/) (2025)
- [DCC: Data-Centric Compilation of Machine Learning Kernels for Processing-In-Memory Architectures](https://mlsanity.com/paper/2511.15503/) (2025)

## Abstract (arXiv)

Genome sequence analysis has enabled significant advancements in medical and scientific areas such as personalized medicine, outbreak tracing, and the understanding of evolution. Unfortunately, it is currently bottlenecked by the computational power and memory bandwidth limitations of existing systems, as many of the steps in genome sequence analysis must process a large amount of data. A major contributor to this bottleneck is approximate string matching (ASM). We propose GenASM, the first ASM acceleration framework for genome sequence analysis. We modify the underlying ASM algorithm (Bitap) to significantly increase its parallelism and reduce its memory footprint, and we design the first hardware accelerator for Bitap. Our hardware accelerator consists of specialized compute units and on-chip SRAMs that are designed to match the rate of computation with memory capacity and bandwidth. We demonstrate that GenASM is a flexible, high-performance, and low-power framework, which provides significant performance and power benefits for three different use cases in genome sequence analysis: 1) GenASM accelerates read alignment for both long reads and short reads. For long reads, GenASM outperforms state-of-the-art software and hardware accelerators by 116x and 3.9x, respectively, while consuming 37x and 2.7x less power. For short reads, GenASM outperforms state-of-the-art software and hardware accelerators by 111x and 1.9x. 2) GenASM accelerates pre-alignment filtering for short reads, with 3.7x the performance of a state-of-the-art pre-alignment filter, while consuming 1.7x less power and significantly improving the filtering accuracy. 3) GenASM accelerates edit distance calculation, with 22-12501x and 9.3-400x speedups over the state-of-the-art software library and FPGA-based accelerator, respectively, while consuming 548-582x and 67x less power.