DNA-Based Storage: Models and Fundamental Limits

Ilan Shomorony, Reinhard Heckel

Abstract

Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In this work, we study the fundamental limits and trade-offs of DNA-based storage systems by introducing a new channel model, which we call the noisy shuffling-sampling channel. Motivated by current technological constraints on DNA synthesis and sequencing, this model captures three key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules; (2) the molecules are corrupted by noise during synthesis and sequencing and (3) the data is read by randomly sampling from the DNA pool. We provide capacity results for this channel under specific noise and sampling assumptions and show that, in many scenarios, a simple index-based coding scheme is optimal.

Introduction

DNA is an incredible storage medium due to its longevity and density, but it doesn't behave like a traditional hard drive. When data is "written" to DNA, millions of short molecules ($M$) are synthesized and stored in a "pool" (a tube of liquid). When reading it back via sequencing, three critical transformations occur:

  1. Shuffling: The spatial order of the molecules is completely lost.
  2. Sampling: We do not read every molecule; we draw a random sample ($N$). Some molecules are read many times, while others are never seen at all.
  3. Noise: Synthesis and sequencing introduce errors (substitutions, insertions, and deletions) into the DNA strings.

This research establishes the theoretical capacity of DNA-based data storage by modeling it as a "noisy shuffling-sampling channel," answering the fundamental question: what is the maximum number of bits we can reliably store per nucleotide given these constraints?

The DNA storage pipeline and its mathematical abstraction as a sample-and-perturb channel.

The Noisy Shuffling-Sampling Channel

The authors define the input as a multi-set of $M$ sequences of length $L$. The channel then samples $N$ sequences according to a distribution $Q$ and applies a Discrete Memoryless Channel (like a Binary Symmetric Channel) to simulate noise.

Key to this analysis is the asymptotic regime where the number of molecules $M$ goes to infinity, and the molecule length $L$ scales as $\beta \log M$. The paper identifies that for DNA storage to be viable, the molecule length $L$ must be at least proportional to $\log M$. If molecules are too short (specifically, if $\beta \leq 1$), the "cost" of indexing consumes the entire molecule, and the achievable rate drops to zero.

Optimality of Indexing

A significant finding of this work is the mathematical validation of common practice. For years, practitioners have used "indexing"—prefixing DNA molecules with unique index tags—to manage the loss of order. This paper proves that this approach is not just a heuristic; it is capacity-optimal.

The index-based coding scheme where molecules are tagged with unique identifiers to combat shuffling.

By using an "outer" erasure code to handle missing molecules (sampling loss) and an "inner" error-correcting code to handle noise within a molecule, this scheme achieves the theoretical limit. The loss in capacity due to shuffling is exactly $1/\beta$, providing a clean mathematical penalty for the unordered nature of the DNA pool.

Key Results and Capacity Limits

The authors derive a closed-form expression for the capacity $C$:

  • Noise-free case: $C = (1 - q_0)(1 - 1/\beta)$ bits per nucleotide, where $q_0$ is the probability a molecule is never sampled.
  • Noisy case (with substitutions): $C = (1 - q_0)(1 - H(p) - 1/\beta)$, where $H(p)$ represents the noise of the DNA sequencing process.

Quantitatively, for a large set of parameters (e.g., error rate $p < 0.1$ and $\beta \geq 6.4$), the index-based approach is the best possible way to store data. The results also characterize the storage-recovery trade-off, showing that increasing sequencing depth ($N/M$) provides diminishing returns for storage density.

Limitations and Future Work

While the proof for substitution errors is robust, a rigorous proof for insertions and deletions—common in technologies like Nanopore sequencing—remains an open challenge. Additionally, there exists a "gray region" of high noise and very short molecules where the optimality of index-based coding is not yet proven. In such extreme regimes, coding across different molecules might be necessary to reach capacity.

Summary updated

Abstract

Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In this work, we study the fundamental limits and trade-offs of DNA-based storage systems by introducing a new channel model, which we call the noisy shuffling-sampling channel. Motivated by current technological constraints on DNA synthesis and sequencing, this model captures three key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules; (2) the molecules are corrupted by noise during synthesis and sequencing and (3) the data is read by randomly sampling from the DNA pool. We provide capacity results for this channel under specific noise and sampling assumptions and show that, in many scenarios, a simple index-based coding scheme is optimal.
BibTeX
@article{shomorony2021dna,
  author = {Ilan Shomorony and Reinhard Heckel},
  title = {{DNA-Based Storage: Models and Fundamental Limits}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=v_PA60SEKel},
}
Figure