Exact Error Exponents of Concatenated Codes for DNA Storage

Yan Hao Ling, Jonathan Scarlett

Introduction

DNA storage offers a revolutionary path toward high-density, long-term data archiving. However, the medium presents unique challenges: data is synthesized into a pool of molecules, sampled (often with replacement), and then sequenced. This process introduces a "shuffling" channel where the original order of data is lost, and some molecules may never be read at all.

While information theorists have characterized the capacity of these systems, engineers require the error exponent to understand how quickly the probability of error vanishes as the number of molecules ($M$) or reads ($N$) increases. Previous research often relied on a "Poisson approximation" to simplify calculations. This paper provides the first exact characterization of error exponents for concatenated codes, demonstrating that previous approximations were significantly loose, especially in high-reliability, low-rate scenarios.

Methodology: Concatenated Codes and Balls-and-Bins

The authors analyze concatenated codes, a practical two-layer architecture:

  1. Inner Code: Protects individual DNA molecules against sequencing errors (e.g., insertions, deletions).
  2. Outer Code: Manages the "set" nature of the data, ensuring recovery even when molecules are missing or sampled multiple times.

The core analysis treats the sequencing process as a classic combinatorial Balls and Bins problem. Imagine $N$ balls (sequencing reads) being thrown into $M$ bins (unique molecules). The error probability is primarily driven by "outage events"—situations where the decoder fails to see enough distinct molecules to differentiate between possible messages. By deriving a new asymptotic formula for the probability of having at most $K$ non-empty bins, the authors calculate exact error exponents across several scaling regimes.

Theoretical Insights: The Poisson Pitfall

A major finding is that the common Poisson approximation underestimates the reliability of DNA storage at low rates. In a multinomial model (where the total number of reads is fixed), the error exponent grows unbounded as the rate approaches zero, whereas the Poisson model suggests a performance ceiling.

Figure 1: Comparison of the exact error exponent function f(c, delta) for Multinomial vs. Poisson models, showing the divergence at low rates.

Furthermore, the paper proves the optimality of "coded-index" strategies. In these strategies, each molecule contains a data payload plus a "tag" or index. This approach attains the highest possible error exponents within the class of concatenated codes. The analysis also reveals that in standard constant-rate regimes, the random sampling process itself—not sequencing noise—is the dominant source of error.

Summary of Key Results

The authors provide a comprehensive mapping of error exponents across different operational regimes, from constant rates to super-linear reads.

Figure 2: Summary of scaling results for the number of messages J and the log error probability across various sequencing error models.
  • Constant Rate Regime: The authors derive an exact function $f(c, \delta)$ for the error exponent, offering a strict improvement over previous bounds.
  • Super-Linear Reads: When the number of reads $N$ grows faster than $M$, the error exponent simplifies to $\log(1/R_0)$, where $R_0$ is the normalized rate.
  • Low-Rate Scaling: The error probability decays as $e^{-\Theta(N \log M)}$, providing a precise "exchange rate" between redundancy and reliability.
  • Noise Model Sensitivity: While sequencing error models (Adversarial vs. Random) have little impact at high rates, they become critical factors in low-rate regimes.

Limitations and Future Outlook

While this work provides exact exponents for concatenated codes, this class of codes may still be suboptimal compared to "full" random coding, which is theoretically superior but computationally impractical. Additionally, the optimal decoding rule identified is likely NP-hard, necessitating future research into computationally efficient decoders. Finally, the current model does not account for "clustering" techniques, where similar-looking reads are grouped together before decoding, which is a common step in real-world DNA storage pipelines.

Summary updated

BibTeX
@article{ling2025exact,
  author = {Yan Hao Ling and Jonathan Scarlett},
  title = {{Exact Error Exponents of Concatenated Codes for DNA Storage}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2025.3581559},
}
Figure