Making it to First: The Random Access Problem in DNA Storage

Avital Boruchovsky, Ohad Elishco, Ryan Gabrys, Anina Gruica, Itzhak Tamo, Eitan Yaakobi · 2025

Read Making it to First: The Random Access Problem in DNA Storage by Avital Boruchovsky, Ohad Elishco, Ryan Gabrys, Anina Gruica, Itzhak Tamo, Eitan Yaakobi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12274.txt.

Introduction

Avital Boruchovsky and co-authors study random access in DNA data storage in a 2025 paper. In such systems, files are written as DNA strands and read back by sequencing, which returns strands in random order. A user who wants one file should not need many reads to recover it, and code design decides that cost.

Data strands are encoded into a larger strand set with a linear code, and each read draws one encoded strand at random. The team fully solves the two file case, giving the best possible code and its expected read count. For three files they extend a known construction, and for four or more files their version beats all past designs. The results guide real DNA archive design.

Catalog record

CREATORAvital Boruchovsky, Ohad Elishco, Ryan Gabrys, Anina Gruica, Itzhak Tamo, Eitan Yaakobi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12274

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Making it to First: The Random Access Problem in DNA Storage Avital Boruchovsky, Ohad Elishco, Ryan Gabrys, Anina Gruica, Itzhak Tamo, Eitan Yaakobi Abstract In this paper, we study the Random Access Problem in DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented by k k information strands which represent the data and are encoded into n n strands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case when k = 2 k=2 , showing that the best possible code attains a random access expectation of 1 + 2 2 + 1 ≈ 0.914 ⋅ 2 1+\frac{2}{\sqrt{2}+1}\approx 0.914\cdot 2 for q q large enough. Moreover, we generalize a construction from [ 19 ] , specifically to k = 3 k=3 , for any value of k k . Our construction uses B k − 1 B_{k-1} sequences over ℤ q − 1 \mathbb{Z}_{q-1} , that always exist over large finite fields. We show that for every k ≥ 4 k\geq 4 , this generalized construction outperforms all previous constructions in terms of reducing the random access expectation. 0 0 footnotetext: A. B. and E. Y. are supported by the European Union (DiDAX, 101115134). Views and opinions expressed are those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. O. E. is supported by the Israel Science Foundation (Grant No. 1789/23). R. G. is supported by NSF Grant CCF2212437. A. G. is supported by the Villum Fonden Grant VIL”52303”. I. T. is supported by the European Research Council (Grant No. 852953). Email addresses: {avital.bor,yaakobi}@cs.technion.ac.il, [email protected], [email protected], [email protected], [email protected] 1 Introduction The exponential growth in data generation has created an unprecedented demand for storage technologies, which current solutions are unable to meet. The gap between data storage demand and the capacity of existing technologies continues to widen at an alarming rate each year [ 27 ] . Addressing this critical challenge has become a global priority, driving the search for innovative and sustainable alternatives. One particularly promising approach is the use of synthetic DNA as a medium for data storage [ 12 , 22 ] . A typical DNA data storage system consists of three primary components: DNA synthesis, storage containers, and DNA sequencing. In the first step, synthetic DNA strands, known as oligos, are generated to encode the user’s information. These strands are then stored in an unordered manner within a storage container. In the final step, DNA sequencing reads the stored strands and converts them into digital sequences, referred to as reads, which are decoded back into the original user information. However, due to limitations in current technologies, the process produces multiple noisy copies of each designed strand, and these copies are retrieved in a completely unordered fashion. While several studies have demonstrated the significant potential of DNA as a data storage medium [ 2 , 8 , 9 , 24 , 29 , 30 , 3 ] , its adoption as a practical alternative to current storage technologies is still limited by challenges related to cost and efficiency. A key factor contributing to these challenges is the coverage depth of DNA storage, defined as the ratio between the number of sequenced reads and the number of designed strands [ 20 ] . Reducing the coverage depth is critical for improving the latency of existing DNA storage systems and significantly lowering their costs. In a recent paper [ 4 ] , Bar-Lev et al. initiated the study of the DNA Coverage Depth Problem , which aims to reduce the cost and latency of DNA sequencing by analyzing the expected number of reads required to retrieve the user’s information. In this model, k information strands, representing the user’s data, are encoded into n strands using a matrix G\in\mathbb{F}_{q}^{k\times n} , often refereed to as a generator matrix of an error-correcting code. The columns of G are then sampled uniformly at random with repetition until the desired information is successfully retrieved (every such sample is referred to as read). The authors considered two variants of this problem: the non-random access setting and the random access setting. In the non-random access setting, the objective is to recover all k information strands, i.e., the entire user’s information. In contrast, the random access setting focuses on retrieving a single, specific strand out of the k information strands. We also remark that a subsequent work [ 1 ] studied a related model in which groups of strands that collectively represent a single file are decoded, rather than individual strands or the entire dataset. By drawing a connection to the classical Coupon Collector’s Problem [ 15 , 16 , 14 , 23 ] , the authors of [ 4 ] showed that when the k information strands are encoded into n strands using an MDS code, then the expected number of reads required to recover all k information strands is H_{n}-H_{n-k} , where H_{i} is the i -th harmonic number. They further proved that no coding scheme can achieve a lower expectation-making MDS codes optimal for minimizing the expected number of reads when the goal is to retrieve the entire data. The non-random access setting was later extended in [ 11 ] to accommodate composite DNA letters [ 2 ] , and further explored in [ 25 , 28 ] in the context of combinatorial composites of DNA shortmers [ 26 ] . A related direction was examined in [ 10 ] , where the authors analyzed the trade-offs between reading costs, tied directly to coverage depth, and writing costs. Finally, [ 5 ] studied the non–random-access setting for codes over small finite fields. In this work, we focus on the random access setting, which remains relatively less understood and presents many open questions. Notably, while MDS codes are optimal in the non-random access setting, they yield an expected number of reads equal to k in the random access case [ 4 ] (that is, the expected number of reads required to retrieve a specific information strand is k ). This is as good (or bad ) as not using any code at all and using the identity code, which also gives a random access expectation equal to k . However, as demonstrated in [ 4 ] , codes with strictly lower expectation do exist. Our goal is to identify and analyze such codes, i.e., those that minimize the expected number of reads required to retrieve any one of the k original strands. Initial steps towards this problem were made in [ 4 ] and [ 18 ] , where constructions, analysis of well-known codes, and bounds on the random access expectation for arbitrary codes were presented. In a later work [ 19 ] , this setting was explored from a geometric perspective, leading to a construction that outperformed

Read the complete text