CS Paper Radar

Representing Information on DNA using Patterns Induced by Enzymatic Labeling

Daniella Bar-Lev, Eitan Yaakobi, Zohar Yakhini, Tuvi Etzion

cs.IT ·submitted 2026-10-16 19:46 UTC · v1
published

Abstract

Enzymatic DNA labeling is a powerful tool with applications in biochemistry, molecular biology, biotechnology, medical science, and genomic research. This paper contributes to the evolving field of DNA-based data storage by presenting a formal framework for modeling DNA labeling in strings, specifically tailored for data storage purposes. Our approach involves a known DNA molecule as a template for labeling, employing patterns induced by a set of designed labels to represent information. One hypothetical implementation can use CRISPR-Cas9 and gRNA reagents for labeling. Various aspects of the general labeling channel, including fixed-length labels, are explored, and upper bounds on the maximum size of the corresponding codes are given. The study includes the development of an efficient encoder-decoder pair that is proven to be optimal in terms of maximum code size under specific conditions. The codewords for this framework are codesets, i.e., each codeword is a collection of a few labels. Of special interest are codes whose codesets contain fixed-length labels. Their construction and analysis are tied to de Bruijn sequences and constrained coding.

Closest papers

Nearest neighbours by meaning across the whole index.

Marker-Delimited Codes for Short-Blocklength, High-Rate Coding over Multi-Read Edit Channels

cs.IT ·2026-08-31 ·Sinan Ates Yercan, Marc Antonini, Serge Kas Hanna
published similarity 0.65
Abstract · 7 pages, 2 figures, This paper has been accepted in IEEE ITW'26

The read process of DNA-based data storage systems generates multiple noisy copies of the stored DNA sequences, affected by edit errors consisting of substitutions, deletions, and insertions. Motivated by the challenge of ensuring reliable data retrieval in the presence of edit errors, we present a concatenated coding scheme that accounts for practical design constraints in DNA storage. We introduce and apply the marker-delimited code (MDC) as the inner code, which enables fast and reliable computation of symbolwise a posteriori probabilities (APPs). We combine MDC with an outer LDPC code. The LDPC is decoded via belief propagation using the soft information generated by MDC. Our results show that, in comparison with prior work, this construction provides more efficient error correction over multi-read edit channels in the short-blocklength and high-rate regime.

0.27

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.63
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

Orthogonal SC-LDPC Codes for the IDS Channel

cs.IT ·2026-10-09 ·Frederik Walter, Jessica Bariffi, Antonia Wachter-Zeh
similarity 0.62
Abstract

We propose a coding scheme for the insertion, deletion and substitution (IDS) channel tailored to the short strands of DNA-based data storage. Instead of an inner synchronisation code, a spatially coupled LDPC (SC-LDPC) code is placed across the strands, with its coupling axis aligned to the position along the strands. Every decoded position thus becomes an anchor to synchronise the neighbouring strands. The decoding waves of the SC-LDPC code carry these anchors from both ends of the strands towards the middle. We bound the achievable rate from above by the information rate of a single strand and from below by that of a separated receiver. For strands of 100 nucleotides (the relevant regime for DNA-based data storage), our scheme outperforms a rate-matched concatenated construction.

0.18

On the Capacity of DNA Labeling in the Single-Label Setting

cs.IT ·2026-09-29 ·Zihan Wu, Qi Cao, Ling Liu, Baoming Bai
unusual similarity 0.59
Abstract

DNA labeling has attracted increasing attention in biomedical applications, including molecular imaging, diagnostics, and genomic analysis. In a DNA labeling process, a set of DNA sequence patterns, referred to as labels, is designed according to the requirements of a specific application. For each DNA sequence, the labeling process generates an output sequence that records the positions of the labels. DNA sequences with different labeling outputs can therefore be distinguished through the labeling process. To quantify this capability, the labeling capacity is defined as the exponential growth rate of the maximum number of DNA sequences that can be distinguished through the labeling process as the sequence length tends to infinity [2]. To date, the labeling capacities of several cases in the single-label setting have been determined. In this paper, we formulate the labeling process as a deterministic channel and show that its zero-error capacity is equal to the labeling capacity. For a single label, the corresponding channel can be represented by a star graph. Thus, characterizing the labeling capacity of a single label is equivalent to determining the zero-error capacity of the corresponding star graph. We derive the zero-error capacities of all star graphs, thereby providing a complete characterization of the labeling capacities for all single-label cases. Furthermore, we develop a general method for constructing capacity-achieving codes. These results apply to labeling problems over arbitrary finite alphabets and are not restricted to the DNA alphabet. Finally, for a fixed label length, we exactly characterize the range of achievable labeling capacities and identify all single-label structures that attain the minimum and maximum capacities.

0.48

BarcodeMAE+: Rethinking Masked Pretraining and Global Representations for DNA Barcode Foundation Models

cs.LG q-bio.GN ·2026-09-26 ·Monireh Safari, Pablo Millan Arias, Scott C. Lowe, Lila Kari, Angel X. Chang +1 more
similarity 0.59
Abstract

Many DNA foundation models are pretrained by masking parts of a sequence and asking the model to reconstruct them. Standard masked pretraining exposes the encoder to special [MASK] tokens that are absent at inference, creating a mismatch between training and downstream use. The role of an explicit global sequence representation such as a [CLS] token and how it should be trained also remain poorly understood for DNA barcodes. We introduce BarcodeMAE+ and study model architecture, global [CLS] representation, and auxiliary pretraining objectives across arthropod COI (BIOSCAN-5M) and fungal ITS (UNITE+INSD) barcodes. Across both barcode regions, the encoder-decoder MAE-LM architecture outperforms its matched encoder-only counterpart in nearly all evaluated configurations, supporting MAE-LM as an effective architectural design for DNA barcode foundation models. A trained global [CLS] representation provides substantial additional gains: on BIOSCAN-5M, [CLS] accuracy increases from 47.53% without an auxiliary objective to 80.65% with cross-entropy genus classification. The best auxiliary objective is region-dependent: cross-entropy performs best on BIOSCAN-5M, whereas pairwise same-genus classification performs best on UNITE+INSD, reaching 73.19% on Yeast and 63.07% on Filamentous Fungi. BarcodeMAE+ outperforms published DNA foundation model baselines on BIOSCAN-5M and achieves the highest Yeast accuracy among the evaluated UNITE+INSD baselines using frozen encoder representations. Similarity-weighted softmax KNN voting further stabilizes accuracy as neighbourhood size increases. Overall, encoder-decoder masked pretraining and an explicitly trained global representation are strong design choices for DNA barcode foundation models, while the optimal objective for learning that representation depends on the biological domain.

0.25

A Hyperbolic Bound for File Retrieval in DNA-Based Data Storage

cs.IT math.CO ·2026-09-28 ·Constantinos Vasilios Argyris Vlachos, Daniella Bar-Lev
theory similarity 0.55
Abstract

In DNA-based storage systems, data are retrieved by sequencing molecules sampled from a DNA pool. We study how the way coding redundancy is shared between files affects their expected retrieval times. Our focus lies on the case of two files that are encoded by a systematic linear code over an arbitrary finite field. We consider the conjecture that the sum obtained by dividing each file dimension by its expected retrieval time is at most one whenever the dimension of at least one file is more than one. For this, we develop a geometric view of the retrieval process. As molecules are sampled, we follow the growing span of the corresponding columns of the generator matrix and track how much of this span comes from each file. Among the samples that enlarge the overall span, this lets us compare those that make progress toward recovering both files with those that make progress toward neither. We call a column mixed if the corresponding encoded symbol combines information from both files. In this work, we sharpen a projection bound and use it to control the effect of mixed columns. We prove the conjecture whenever the total information dimension is at least twice the number of mixed columns plus two. For equal-sized files, this allows up to one fewer mixed column than the dimension of either file and extends the previous result for codes with no mixed columns.

0.40

Pangenome Optimization via Elastic Degenerate Strings

cs.DS ·2026-09-22 ·Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen
code/data similarity 0.54
Abstract

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

0.39

Probabilistic GC-Constraints for Composite DNA

cs.IT ·2026-10-07 ·Humeyra Bodur, Frederik Walter, Antonia Wachter-Zeh
similarity 0.54
Abstract

This paper addresses the challenge of encoding biochemical GC-content constraints in composite DNA-based data storage. Previous deterministic models impose high rate penalties by avoiding any possibility for a strand to fall outside the allowed range. To account for the stochastic nature of composite DNA, we introduce an $ε$-probabilistic constraint framework, and derive capacity bounds for global constraints using composition types and for local sliding-window constraints via finite-state Markov chains. Furthermore, we propose a capacity-achieving multi-type enumerative encoder.

0.25