Error Exponents for DNA Storage Codes with a Variable Number of Reads
Yan Hao Ling, Nir Weinberger, Jonathan Scarlett · 2025
Read Error Exponents for DNA Storage Codes with a Variable Number of Reads by Yan Hao Ling, Nir Weinberger, Jonathan Scarlett (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-2504-17337.txt.
Introduction
Yan Hao Ling, Nir Weinberger, and Jonathan Scarlett study in 2025 how the error rate of DNA data storage codes improves when the reader may choose how many reads to take. In DNA storage, data are written into synthetic strands and read back by sequencing. Each read is costly and noisy, so the count of reads matters.
Fixed read plans decide the count in advance. A flexible plan reads one batch at a time and stops when it is sure enough, which cuts the average count. The team shows this freedom lowers the error chance a lot, in the fine constants and in the scaling law itself. They prove a design that gains the benefit, and in some ranges a matching proof that no plan in a broad class can do better.
Catalog record
| CREATOR | Yan Hao Ling, Nir Weinberger, Jonathan Scarlett |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17337
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Error Exponents for DNA Storage Codes with a Variable Number of Reads Yan Hao Ling, Nir Weinberger, Jonathan Scarlett Abstract In this paper, we study error exponents for a concatataned coding based class of DNA storage codes in which the number of reads performed can be variable. That is, the decoder can sequentially perform reads and choose whether to output the final decision or take more reads, and we are interested in minimizing the average number of reads performed rather than a fixed pre-specified value. We show that this flexibility leads to a considerable reduction in the error probability compared to a fixed number of reads, not only in terms of constants in the error exponent but also in the scaling laws. This is shown via an achievability result for a suitably-designed protocol, and in certain parameter regimes we additionally establish a matching converse that holds for all protocols within a broader concatenated coding based class. I Introduction In recent years, significant research attention has been paid to characterizing the capacity of DNA storage systems; see [ 1 ] for a recent overview. While capacity is perhaps the most fundamental notion of a performance limit, it is limited by its lack of consideration of how quickly the error probability approaches zero as the problem size increases. This limitation is addressed by studies of error exponents , which characterize the exponential decay rate of the error probability at rates below capacity. Error exponents have long been studied for channel coding problems [ 2 , 3 ] , and were recently studied for DNA storage in [ 4 , 5 , 6 ] . In more detail, [ 4 ] studied error exponents of random codes, whereas [ 5 , 6 ] focused on a class of concatenated codes in which an an “inner code” for the sequencing channel is used in a black-box manner for individual molecules, and an “outer code” is used to handle the entire set of molecules. This class of codes is practically well-motivated, since the inner code can make use of well-established techniques from point-to-point channel coding. Moreover, in [ 5 , 6 ] the sequencing channel need not be a discrete memoryless channel as was assumed in [ 4 ] ; for example, insertions and deletions can be considered. While the results of [ 6 ] (building on [ 5 ] ) provide exact (i.e., optimal) error exponents for a class of concatenated codes under a standard setup, they turn out to leave significant room for improvement under a minor modification of the setup. In particular, the error exponent is dominated by the event that there are unusually few distinct molecules sampled, and correspondingly, their converse result holds even when the sequencing error probability is zero . This suggests that the performance could be significantly improved by allowing a variable number of reads , so that more reads can be performed when needed, without increasing the average number of reads too much. In this paper, we make this intuition precise by studying error exponents of concatenated codes under a variable number of reads, where we now consider the average number of reads instead of a pre-specified number. We show that this setup permits a considerably smaller error probability, and we attain matching achievability and converse results in certain regimes of interest. I-A Contributions We introduce our problem setup and notation in Section II , but for the purpose of outlining our contributions, we note that we will consider codewords containing M molecules of length L , let N denote the number of reads performed, and let p denote the sequencing error probability. Our contributions are: • We follow the setup of [ 5 , 6 ] with concatenated coding and an index-based inner code (see Section II ). Under the standard scaling choices L=\Theta(\log M) , \mathbb{E}[N]=\Theta(M) , and p=o(1) , we show that the error probability with a variable number of reads decays as e^{-\Theta(M\log\frac{1}{p})} , thus being significantly smaller than e^{-\Theta(M)} with a fixed number of reads. This result holds for all coding rates that are achievable via the coding techniques in [ 5 , 6 ] (our techniques in this paper will have the same set of achievable rates). • We establish an achievable error exponent (i.e., specifying the hidden constant in \Theta(\cdot) notation in e^{-\Theta(M\log\frac{1}{p})} ), and in certain parameter regimes we additionally give a matching converse, thus establishing the exact error exponent in the variable-reads setting. • Our bounds hold under suitably-defined adversarial models of sequencing errors, and we consider two kinds of adversary: A “strong adversary” that knows the decoder and can see into the future (e.g., knowing exactly when sequencing errors will occur), and a “weak adversary” that only knows the message and codebooks, and must act solely based on the past. Our achievability result (Theorem 7 ) holds even under the strong adversary, and our converse is proved first for the strong adversary (Theorem 8 ) and then for the weak adversary (Theorem 9 ). Before proceeding to the problem setup, we make some remarks to help set the context for our results within the existing literature: • The class of codes that we consider is motivated by previous practical and theoretical uses of concatenated codes for DNA storage (e.g., [ 7 , 8 ] ). We refer the reader to [ 5 ] for further discussion on the practical motivation. • While the concatenated codes that we consider are powerful and well-motivated, we note that they can be suboptimal, precluding certain advanced techniques such as clustering [ 1 , Sec. 5.1] and “full” random coding [ 4 ] . In particular, the exponent is only positive for rates up to a certain threshold that can be strictly worse than the one in [ 4 ] (see ( 7 ) below). • Similarly to the related works [ 4 , 5 , 6 ] , our work is complementary to the extensive work on coding-theoretic considerations for DNA storage codes (e.g., see [ 9 , 10 , 11 ] and the references therein), which typically seek distinct goals such as good distance properties. II Problem Setup We follow the problem setup from [ 5 , 6 ] , while allowing a variable number of reads. For completness, we provide the full description. II-A Basic Notation We adopt a standard information-theoretic model of DNA storage, with the building blocks being as follows: • The goal is to reliably store and recover a message m drawn uniformly at random from a finite set of messages. • A molecule is a length- L string whose symbols come from some finite alphabet \mathcal{X} (e.g., \mathcal{X}=\{A,C,G,T\} ). • Each message is associated with an unordered collection of M input molecules that are stored. This collection is referred to as the (outer) codeword for m . • At the decoder, N reads are performed. For each read, (i) one of the M input molecules is sampled uniformly at random; and (ii) the molecule in \mathcal{X}^{L} is passed through a sequencing channel (independently of all other reads) and the decoder sees the output, whose alphabet we denote by \mathcal{Y}^{(L)} . For example, the channel might