# GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2017.

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

- [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)
- [Machine Learning Training on a Real Processing-in-Memory System](https://mlsanity.com/paper/2206.06022/) (2022)
- [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)
- [AGNES: Adaptive Graph Neural Network and Dynamic Programming Hybrid Framework for Real-Time Nanopore Seed Chaining](https://mlsanity.com/paper/2510.16013/) (2025)
- [DCC: Data-Centric Compilation of Machine Learning Kernels for Processing-In-Memory Architectures](https://mlsanity.com/paper/2511.15503/) (2025)

## Abstract (arXiv)

Motivation: Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locations for seeds (i.e., smaller segments) within each read, 2) extract reference sequences at each of the mapping locations, and 3) check similarity between each read and its associated reference sequences with a computationally-expensive algorithm (i.e., sequence alignment) to determine the origin of the read. A seed location filter comes into play before alignment, discarding seed locations that alignment would deem a poor match. The ideal seed location filter would discard all poor match locations prior to alignment such that there is no wasted computation on unnecessary alignments. Results: We propose a novel seed location filtering algorithm, GRIM-Filter, optimized to exploit 3D-stacked memory systems that integrate computation within a logic layer stacked under memory layers, to perform processing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1) introducing a new representation of coarse-grained segments of the reference genome, and 2) using massively-parallel in-memory operations to identify read presence within each coarse-grained segment. Our evaluations show that for a sequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the false negative rate of filtering by 5.59x--6.41x, and 2) provides an end-to-end read mapper speedup of 1.81x--3.65x, compared to a state-of-the-art read mapper employing the best previous seed location filtering algorithm. Availability: The code is available online at: https://github.com/CMU-SAFARI/GRIM