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 presents unique challenges compared to traditional magnetic or solid-state drives. In a hard drive, bits are stored in fixed physical locations. In DNA storage, data is stored in a "soup" of molecules, leading to several distinct constraints:

  1. Fragmentation: Data must be written across millions of short molecules ($M$ molecules of length $L$).
  2. Unordered Storage: Molecules are kept in a pool, losing their spatial order (shuffling).
  3. Random Sampling: Reading involves drawing $N$ samples from the pool; some molecules are read multiple times, while others may be missed entirely.
  4. Noise: Synthesis and sequencing introduce errors like substitutions, insertions, and deletions.

To address these, the authors propose the noisy shuffling-sampling channel, a mathematical model that captures the end-to-end process of DNA data storage.

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

The Indexing Strategy and Scaling Laws

A central challenge in DNA storage is the loss of order. If we store a file across many fragments, we must include a way to reconstruct the original sequence. The authors analyze a regime where molecule length $L$ scales with the number of molecules as $L = \beta \log M$.

A key insight is that the "index" or "address" of a molecule is the fundamental price of admission for this medium. Since an index requires $\log M$ bits, and the total length is $\beta \log M$, the index consumes exactly $1/\beta$ of the molecule's capacity. The paper proves that this overhead is the fundamental "tax" paid for the loss of ordering.

The indexing strategy where each molecule is tagged with a unique address to overcome the loss of ordering.

The researchers show that a simple strategy—tagging each molecule with its address and using an outer erasure code to handle missing molecules—is actually capacity-optimal in many scenarios. This suggests that complex joint coding across different molecules is often unnecessary to reach the theoretical limits of the channel.

Capacity Results

The paper establishes theoretical "speed limits" for DNA storage by deriving capacity expressions ($C$), representing the maximum bits reliably stored per nucleotide.

  • Noise-Free Capacity: $C = (1 - q_0)(1 - 1/\beta)$, where $q_0$ is the fraction of molecules never sampled.
  • Noisy Capacity (Low-Error Regime): $C = (1 - q)(1 - H(p) - 1/\beta)$, where $H(p)$ is the entropy of substitution noise.

These results hold when the noise is low enough (e.g., error probability $p \le 0.1$ and $\beta \ge 6.4$). If molecules are too short ($\beta \le 1$), the capacity drops to zero because the molecule cannot even contain its own address.

Conclusion and Future Work

While this work provides a rigorous foundation for DNA storage, several challenges remain. The current model primarily focuses on substitution errors, whereas real DNA systems are heavily affected by insertions and deletions (indels). Extending these capacity results to indel channels is a major open problem. Additionally, in extremely high-noise regimes, the optimality of simple indexing may no longer hold, potentially requiring more sophisticated coding techniques that operate across multiple sequences.

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