RapidGKC: GPU-Accelerated K-Mer Counting
Yiran Cheng, Xibo Sun, Qiong Luo
Abstract
Many bioinformatics applications, e.g., genome assembly, genome profiling, and sequence alignment, break biological sequences into k-mers, or length-k substrings, for sub-sequent processing. In these applications, counting the number of occurrences of distinct k-mers is a common but expensive step due to the data and computation intensity. As such, prior work proposed to parallelize this task and utilize GPUs for further acceleration. However, these solutions under-utilize the GPU parallelism because the encoding format of intermediate data forces sequential decoding. To address this problem, we design a new encoding scheme for variable-length genomic data to support parallel encoding and decoding. Furthermore, we propose a novel rule to select common substrings among k-mers for partitioning, reducing the space cost as well as facilitating efficient parallel processing. Finally, we parallelize the entire workflow of partitioning and counting through pipelining, CPU-GPU co-processing, and work stealing. As a result, RapidGKC, our end-to-end GPU-accelerated k-mer counting system, outperforms state-of-the-art CPU-based and GPU-accelerated methods on real-world datasets.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- AGAThA: Fast and Efficient GPU Acceleration of Guided Sequence Alignment for Long Read MappingSeongyeon Park, Junguk Hong, Jaeyong Song, Hajin Kim et al.PPoPP 2024 · 7 citations
- Sieve: Scalable In-situ DRAM-based Accelerator Designs for Massively Parallel k-mer MatchingLingxi Wu, Rasool Sharifi, Marzieh Lenjani, Kevin Skadron et al.ISCA 2021 · 31 citations
- Accelerating large scale de novo metagenome assembly using GPUsMuaaz Gul Awan, Steven Hofmeyr, Rob Egan, Nan Ding et al.SC 2021 · 6 citations
- FastZ: accelerating gapped whole genome alignment on GPUsSree Charan Gundabolu, T. N. Vijaykumar, Mithuna ThottethodiSC 2021 · 10 citations
- PMKLC: Parallel Multi-Knowledge Learning-based Lossless Compression for Large-Scale Genomics DatabaseHui Sun, Yanfeng Ding, Liping Yi, Huidong Ma et al.KDD 2025
