CS Paper Radar

In-depth data movement characterization of DNA read mapping algorithms

Berkan Şahin, Ecem İlgün, Klea Zambaku, Can Alkan

cs.AR q-bio.GN ·submitted 2026-11-02 16:31 UTC · v1
top venue

Abstract

Read mapping algorithms represent a critical bottleneck in genomic analysis pipelines due to the resources required; a problem that is becoming more pronounced as sequencing technologies advance and datasets expand. We present an extensive workload characterization of leading read mapping algorithms across diverse sequencing technologies to identify hardware acceleration and optimization opportunities. We analyzed the following implementations: MashMap, wfmash, and Minimap2 for whole-genome alignment (WGA); NGMLR, Minimap2, and LRA for long reads; and Bowtie2, BWA-MEM, StrobeAlign, and minibwa for short reads. We used the Intel VTune Profiler for detailed memory analysis to identify memory- bound functions, cache usage patterns, and data transfer bottlenecks. We further analyzed a selected subset of alignment tools using the DAMOV-SIM simulator to obtain a more granular view of data movement characteristics for two different cache structures. Based on our results, Minimap2 emerges as the fastest alignment tool for long read scenarios, but falls behind in whole-genome alignment due to poor multithreading. Across all three categories, some programs (e.g., LRA, BWA-MEM) are highly memory-bound. More in-depth analysis via DAMOV-SIM revealed that some memory-bound tools, in particular, do not fully utilize the multi-level cache hierarchy in modern multi-core CPU architectures. Our results show that while some tools require algorithmic redesign for performance gains, some others can benefit from running on PIM architectures.

Closest papers

Nearest neighbours by meaning across the whole index.

Benchmarking Traditional and Learning-Based Reference-Free Compressors for Long-Read Sequencing Data

cs.IT q-bio.GN ·2026-11-18 ·Huidong Ma, Hui Sun, Xinyan Shi, Cheng Zhong, Xiaoguang Liu +1 more
surveybenchmark similarity 0.67
Abstract

Long-read sequencing technologies generate large volumes of data, creating substantial storage and transmission demands. Although reference-based compressors can achieve high compression, their reliance on an appropriate reference genome limits their use. We present LRCBench, a benchmark and survey of reference-free lossless compressors for long-read sequencing data. We review traditional and learning-based general-purpose and sequencing-specific methods, then evaluate 35 compressors on 16 real-world datasets from Oxford Nanopore and PacBio platforms. We compare compression ratio, storage savings, runtime, peak memory use, and robustness across datasets. Learning-based compressors are evaluated on six MinION datasets because of their high computational costs. CoLoRd achieves the best overall compression ratios in our experiments, while other methods offer trade-offs in speed, memory use, and robustness. We also examine multithreaded speedup and discuss future directions in parallel acceleration, privacy protection, adaptive parameter tuning, and hardware-algorithm co-design.

0.28

HORIZON: A Read-Efficient Firmware for DNA Storage with Horizontal Layout

cs.ET ·2026-08-25 ·Alex Sensintaffar, Roop Kiran, Yang Chen, Mai Zheng, Bingzhe Li
similarity 0.65
Abstract

DNA storage is a promising medium for long-term archiving, but its read performance is limited by coarse-grained random access. Existing random-access DNA storage designs suffer from high read amplification because their sequential layouts co-locate frequently and infrequently accessed data under the same primer pair, where any read must retrieve all associated strands even when only a small fraction is needed. We present HORIZON, a read-efficient allocation policy for DNA block devices that reduces read amplification through activity-aware horizontal placement. HORIZON first introduces a horizontal layout distributing writes round-robin across primer pairs, rather than filling each sequentially. It classifies newly written blocks in the write buffer as active or inactive, tracks recent primer-pair accesses using a sliding-window temperature model, and allocates blocks based on block activity and primer-pair occupancy. Simulations show HORIZON consistently reduces read amplification compared with state-of-the-art schemes across MSR and FIU traces and synthetic filesystem workloads.

0.29

Democratizing Clinical Tumor Whole Genome Sequencing: 18-hour End-to-end Analysis via Trillion-parameter Large Language Models Locally Deployed on Consumer-grade Hardware

cs.LG q-bio.GN ·2026-09-14 ·Rui Xiao, Yili Xu
similarity 0.61
Abstract · 11 pages. Corresponding author: Yili Xu(22465225@qq.com)

Whole genome sequencing (WGS) is essential for precision oncology, yet its clinical adoption remains limited by prohibitive computational costs and multi-day turnaround times. This work presents a fully localized low-resource framework enabling stable deployment of a trillion-parameter biomedical LLM on a single consumer-grade RTX 4060 laptop with 32GB system memory and 8GB VRAM, as well as on routine clinical workstations in general hospitals, completing the entire tumor-paired WGS workflow from raw FASTQ input to clinical-grade full-variation-spectrum report output. Under standard 30X depth configurations, our implementation finishes a single tumor-paired WGS analysis within 18 hours, achieving 99.62% F1 score for somatic variant detection with over 99.9% concordance to the industrial-standard A100 cluster pipeline, fully meeting clinical oncology accuracy requirements. Quantitative profiling shows adaptive heterogeneous memory scheduling accounts for 71% of total execution time, while model optimization introduces less than 9% of total detection error. This work is the first engineering implementation of trillion-parameter biomedical LLM-driven clinical-grade genomic analysis on consumer-grade hardware, breaking the industry paradigm that trillion-scale genomic LLMs require hundred-thousand-dollar GPU clusters and multi-day turnaround, establishing a low-resource pathway for global primary medical institutions to adopt whole-genome precision oncology at zero additional cost.

0.12

Storage-Centric System Designs for Enabling Fast, Efficient, and Low-Cost Genomic and Metagenomic Analyses

cs.AR cs.DCq-bio.GNq-bio.QM ·2026-08-31 ·Nika Mansouri Ghiasi
highly cited similarity 0.60
Abstract

Genomic and metagenomic analyses play critical roles in many fields, such as precision medicine, urgent clinical settings, discovering early warnings of communicable diseases, ensuring food safety through pathogen monitoring, agriculture, and scientific discovery. Due to the challenges of analyzing and storing massive volumes of genomic and metagenomic sequence data, significant efforts have been made to accelerate (meta)genomic analyses and store sequence data compressed. Despite the benefits of these techniques, we identify two major outstanding problems in accessing stored sequence data and supplying it to the analysis units: (i) the data movement bottleneck due to moving large amounts of low-reuse data from storage and the unnecessary burden on the rest of the system, and (ii) the data preparation bottleneck, where compressed sequence data needs to be first decompressed and formatted before analysis. In this dissertation, we present customized storage-centric systems, which efficiently (i) analyze (meta)genomic data inside the storage system, and (ii) enable highly-compressed storage and high-performance access of large-scale sequence data, thereby alleviating the overheads of data movement, computation, and data preparation. We demonstrate that the proposed systems significantly improve system performance, energy efficiency, and system cost-efficiency of (meta)genomic analysis. We hope that the storage-centric systems proposed in this dissertation facilitate the broader adoption of (meta)genomic analyses and inspire future research to fundamentally improve the performance, energy efficiency, and cost-effectiveness of other data-intensive application domains related to health and life sciences.

0.51

ACOR: incremental evidence accumulation towards real-time DNA storage reconstruction

cs.IR q-bio.GN ·2026-10-27 ·Linxuan Han, Huaming Wu, Shi Jia, Guanjin Qu
benchmark similarity 0.60
Abstract

DNA offers high-density, durable storage by encoding digital information into synthetic strands and retrieving it through sequencing. Sequence reconstruction combines noisy copies of each strand before downstream decoding. Conventional offline methods typically reconstruct completed read clusters, separating reconstruction from ongoing read collection. Streaming reconstruction offers a way to overlap evidence processing with sequencing and reduce the computation remaining before downstream decoding. We present ACOR, a streaming consensus reconstruction method that records $k$-mer transitions and boundary support in a persistent ledger, then decodes through length-constrained beam search and priority-based selection at cluster closure. Evaluation on real and simulated DNA-storage datasets showed competitive recovery. On our own short-read next-generation sequencing (NGS) wet-lab library, ACOR combined near-complete recovery with second-scale reconstruction of more than ten million reads. A smaller public benchmark was completed in a fraction of a second. Parallel ACOR achieved speedups of tens to over a thousand-fold relative to the tested serial baseline configurations. Sparse storage reduced high-context memory requirements, while parallel execution accelerated reconstruction computation. ACOR is designed for streaming readout pipelines that process assigned reads while sequencing continues.

0.23

The Unified Evaluation App for DNA Data Storage Codecs

cs.ET cs.SE ·2026-08-10 ·Aleksandar Anžel, Chisom Anyabolu, Leon Wimbes, Luca Staus, Ihsan Tri Heldian +10 more
code/data similarity 0.59
Abstract · 38 pages, 12 figures

Background: Deoxyribonucleic acid (DNA) data storage is a paradigm with great potential for ultra-dense and durable information preservation. However, the rapid proliferation of coding schemes, or codecs, each with their own design constraints and reporting practices, has led to a fragmented landscape that lacks a standardized comparative assessment. Methods: We developed an open-source, modular benchmarking platform that systematically integrates and evaluates state-of-the-art DNA storage encoding and decoding methods (codecs). Our approach uses a curated, diverse set of baseline data and applies multidimensional assessment criteria that are aligned with the consensus standard of the DNA Data Storage Alliance. These criteria include encoding/decoding throughput, computational efficiency, error correction performance across substitutions, insertions, and deletions, and cost efficiency. Results: The developed platform integrates standardized wrapper functions for encoding and decoding, allows for the integration of new methods, and automates reproducible evaluations with comprehensive visual and tabular reporting. Benchmarking both contemporary and classical codecs using their default parameters and multiple metrics demonstrates that no single algorithm is optimal across all evaluated dimensions. The trade-offs between information density, success rate, runtime, and cost are quantified and shown to be critical factors in the design of future-proof formats. Conclusions: Our work establishes a rigorously standardized, open-source evaluation framework that enables reproducible benchmarking, supports evidence-based codec selection, and provides the necessary foundation for translating DNA data storage from experimental research into deployable archival systems.

0.26

ShiftCache: Fast and Exact Indel Effect Prediction by Reusing Shifted Reference Encodings

cs.LG cs.DC ·2026-11-09 ·Sina Barazandeh, Arth Banka, Jose Lugo-Martinez
similarity 0.59
Abstract · 31 pages, 7 figures, 8 tables, including appendix

Sequence-to-function models such as AlphaGenome and Borzoi read up to a megabase of DNA and score a genetic variant by comparing their predictions for the reference and alternate sequences. Insertions and deletions (indels) are costly to score, because an indel usually shifts the unchanged DNA after it onto a different pooling grid, which prevents direct reuse of the reference's encoder activations. The AlphaGenome Atlas scored more than 100 million indels with three full model passes each, although the DNA after an indel matches the reference shifted by the indel's length. We present ShiftCache, an exact reuse system that encodes each shifted reference once and shares it among all variants scored in the same window with the same shift. ShiftCache copies every encoder output a variant can reuse and recomputes the rest in batched tiles. On held-out AlphaGenome windows shared by many indels, in strict fp32 on one A6000, ShiftCache is 3.5 to 6.5$\times$ faster than deduplicated dense execution and 1.6 to 2.7$\times$ faster than our adaptation of layer-by-layer reuse to indels. It is 3.5 to 4.1$\times$ faster than dense reimplementations of two published analyses with Borzoi and AlphaGenome, and 2.6$\times$ faster than dense execution with Enformer. Scoring each variant in its own centered 131 kb window makes ShiftCache only 1.36$\times$ faster than deduplicated dense execution, and highly diverse insertion lengths or many dispersed edits can make it slower than layer-by-layer reuse or dense execution. For encoders that meet our conditions, ShiftCache computes the same predictions as dense execution in exact arithmetic. On an A6000, every checked output of the default AlphaGenome and Borzoi runs matches dense execution within an absolute and relative tolerance of $10^{-5}$. With larger tile batches, with Enformer or on an H100, a small fraction of values exceeds this tolerance.

0.32

AlignPred: Error-Controlled KV Cache Compression via Alignment and Predictive Coding

cs.PF cs.LG ·2026-10-13 ·Xu Yang, Jiapeng Zhang, Zhiwei Zuo, Yuxin Chen, Feiqiang Sun +3 more
similarity 0.58
Abstract

Long-running agents retain KV caches across turns and sessions for hours or days. Compressing these persistent caches requires reducing storage while controlling reconstruction error. We present AlignPred, a codec that combines local alignment with predictive coding under a configurable KV reconstruction-error budget. Local orthogonal transforms align related heads or layers into a common coordinate frame, allowing AlignPred to combine token-wise prediction with same-token prediction across heads or layers. Residuals are quantized on an error-bounded lattice and entropy-coded, without learned predictors, encoder-side mode search, or large joint transforms. Across three attention mechanisms, AlignPred requires less storage than the evaluated baselines at comparable measured reconstruction error. Against the evaluated CPU codec implementations, it decodes at least 1.6 times faster while matching or improving encode time. AlignPred achieves near-native task scores at substantially compressed operating points on LongBench-Pro at 128K context. AlignPred's SGLang HiCache integration reduces persistent target-KV storage by 42-72% relative to native HiCache, with comparable latency.

0.46