Source-linked AI summary
Fundamental Limits of DNA Storage Systems
Reinhard Heckel, Ilan Shomorony, Kannan Ramchandran, David N. C. Tse
TL;DR
DNA offers longevity and high information density for archival storage, but synthesis and sequencing impose constraints. The paper analyzes an unordered-molecule storage model and finds that index-based coding is optimal, while identifying losses from unseen molecules and unordered reading.
Problem
The paper studies fundamental storage-capacity limits and tradeoffs for DNA archives amid technological constraints on synthesis and sequencing.
Source: §1 · pp. 1–2Method
Results
The capacity analysis identifies losses from unseen molecules and unordered reading, and shows that indexing molecules with optimal cross-molecule erasure coding is information-theoretically optimal.
Source: §1 · p. 2Takeaways & Limitations
The capacity expression suggests avoiding very high coverage because sequencing costs can be exorbitant for only marginal capacity gains.
Source: §1 · p. 2The model assumes molecules are read and written without error or storage damage, and the effect of index errors on the capacity-achieving scheme is uncertain.
Source: §5 · p. 9
Abstract
from arXiv · showhide
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 tradeoffs of DNA-based storage systems under a simple model, motivated by current technological constraints on DNA synthesis and sequencing. Our model captures two key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the data is read by randomly sampling from this DNA pool. Under this model, we characterize the storage capacity, and show that a simple index-based coding scheme is optimal.
1 Introduction
DNA is presented as a promising archival medium because of its longevity and information density, despite synthesis and sequencing constraints. The paper analyzes storage capacity for unordered pools of short molecules read by random sampling and establishes the optimality of index-based coding.
1 Introduction
- Current synthesis and sequencing technologies constrain practical DNA molecules and reads to lengths of a few hundred nucleotides, while longer-read technologies have higher error rates and costs.The passage notes that longer reads are also unnecessary given current synthesizable lengths.Source: §1 · p. 1
- The model writes M molecules of length L and reads N times uniformly with replacement, without telling the decoder which molecules were sampled.Unless N = Ω(M log M), some original fragments are never sampled; the analysis assumes error-free reads and N = cM as M grows.Source: §1 · p. 2
- The capacity analysis separates losses from unseen molecules, 1−e−c, and unordered reading, 1−1/β; below β=1, no positive rate is achievable.The model considers β = lim L log M.Source: §1 · p. 2
- Indexing each molecule and applying an optimal erasure code across molecules is information-theoretically optimal.Prefixing each molecule with a unique header incurs no rate loss.Source: §1 · p. 2
- Very high coverage c can impose substantial sequencing time and cost for only marginally better capacity, especially when N = Ω(M log M).In that regime, each sequence is read at least once.Source: §1 · p. 2
- Unlike, which assumes indexed molecules and reduces the channel to an erasure channel, this work focuses on unordered molecules read by random sampling.[EZ17] considers other constraints, including homopolymer limitations.Source: §1 · pp. 2–3
2 Problem Setting
The model stores each codeword as an unordered multiset of DNA strings and reads it through independent random sampling with replacement. It studies storage and recovery rates as the number of stored molecules grows under fixed coverage depth.
2 Problem Setting
- An (M, L, N) DNA storage code is a set of codewords, each a multiset of M length-L strings, together with a decoding procedure.The exposition focuses on the binary alphabet, with results extendable to a general alphabet.Source: §2 · p. 3
- The decoder obtains N molecules by independent uniform sampling with replacement from the M stored molecules.The resulting samples form a multiset that the decoder maps to a message index.Source: §2 · pp. 3–4
- Storage rate is the number of bits written per DNA base synthesized.Source: §2 · p. 4
- Recovery rate is the number of bits recovered per DNA base sequenced.Source: §2 · p. 4
- As M grows with fixed coverage depth c, the model sets molecule length L to β log M and defines achievable rates by vanishing decoding error.Here c = N/M, and L = Ω(log M) is identified as the asymptotic regime of interest.Source: §2 · p. 4
3 Storage Capacity
The storage capacity is achieved by a simple index-based scheme and is optimal; no positive rate is possible when β ≤ 1. The converse combines bounds on the number of molecule types with a genie-aided channel that preserves the sampling ambiguity relevant to the original system.
3 Storage Capacity
- Theorem 1 characterizes capacity: the index-based rate (1 − e^-c)(1 − 1/β) is optimal, and no positive rate is achievable when β ≤ 1.Distinct log M-bit tags leave L − log M symbols per molecule for data and turn sampling into an erasure channel.Source: §3 · p. 4
3.1 Motivation for Converse
- Counting possible molecule types shows that no positive storage rate is possible when L/log M has limit below 1, while the converse combines this bound with a sampling bound.The counting argument motivates the converse; the combined bounds establish the optimality of index-based coding.Source: §3.1 · p. 5
3.2 Converse
- A genie appends unique random indices before sampling, enabling a converse without revealing which stored molecule produced each read.The expected fraction of distinct molecules observed tends to 1 − e^-c; the genie’s output retains the ambiguity of equal samples from duplicate molecules.Source: §3.2 · pp. 5–6
- The converse bounds the achievable rate using the number of possible frequency vectors among the molecules observed by the decoder.The argument uses a high-probability bound on the number of observed molecules and a type-count bound.Source: §3.2 · pp. 6–7
4 Storage-Recovery Tradeoff
The storage-recovery feasibility region expresses the tradeoff between storage rate and sequencing requirements. Modest coverage depths capture most of the storage rate, while a separate cost calculation identifies an operating point for a specified synthesis-to-sequencing cost ratio.
4 Storage-Recovery Tradeoff
- Coverage depths c = 1, 2, and 3 achieve 63%, 86%, and 95% of the storage rate, respectively, unlike the deep sequencing used in developed practical systems.The authors suggest modest coverage rather than maximizing storage rate, which technically requires c → ∞.Source: §4 · p. 8
- For synthesis costs q = 10000 times sequencing costs, the cost-minimizing coverage depth is approximately c = 9.2.The stated synthesis-to-sequencing cost ratio is q = 10,000–100,000; the example uses q = 10000.Source: §4 · p. 8
- At β = 5, Figure 4 presents the feasible (R_s, R_r) storage-recovery region, derived from the capacity result and R_s = cR_r.The region makes the storage-rate and recovery-rate tradeoff explicit.Source: Figure 4 · p. 8, §4 · p. 8
5 Concluding Remarks
The paper studies fundamental limits under a DNA-storage model inspired by current synthesis and sequencing technologies, showing that index-based coding is asymptotically optimal. It also identifies modeling assumptions and regimes for further study.
5 Concluding Remarks
- Under the proposed model, a simple index-based coding scheme is asymptotically optimal.The model is inspired by current DNA synthesis and sequencing technologies.Source: §5 · p. 8
- The model assumes molecules are written and read without errors or storage damage, limiting its realism.Errors in indices could disrupt block ordering and prevent reducing the channel effectively to an erasure channel.Source: §5 · p. 9
- Equal PCR amplification is unrealistic, especially when the number of PCR cycles is large.A more realistic model could use a non-uniform molecule distribution, such as Poisson.Source: §5 · p. 9
- The authors identify very short molecules and, as synthesis evolves, long molecules as regimes for future modeling.They note that significant data can be stored with very short molecules despite the paper's result that no rate is achievable when β ≤1.Source: §5 · p. 9
Funding and Acknowledgements
The acknowledgements report research support, visiting appointments, and thanks to colleagues for discussions and comments.
Funding and Acknowledgements
- RH received Swiss National Science Foundation support, while IS and DT received support from the Center for Science of Information.The reported grants are P2EZP2 159065 and CCF-0939370, respectively.Source: Funding and Acknowledgements · p. 9
- IS and DT completed part of the work while visiting the Simons Institute, and IS held a Simons Research Fellowship.The authors also thank Olgica Milenkovic for discussions on DNA-based storage.Source: Funding and Acknowledgements · p. 9
- The authors thank Yaniv Erlich for manuscript comments, Jossy Sayir for pointing them to, and Robert Grass for discussions.Source: Funding and Acknowledgements · p. 9
6 Appendix
The appendix proves two lemmas using a combinatorial correspondence and a coupon-collection argument. The latter relates distinct sampled molecules to the output frequency vector and bounds deviations using Chebyshev's inequality.
6.1 Proof of Lemma 1
- For Lemma 1, vectors with nonnegative entries summing to b correspond one-to-one with binary strings containing a−1 zeros and b ones.The proof counts these strings and invokes a standard binomial-coefficient bound.Source: §6.1 · p. 10
6.2 Proof of Lemma 2
- The ℓ1 norm of the output frequency vector is distributed as the number of distinct coupons in M-item sampling with replacement.This correspondence is used to establish Lemma 2.Source: §6.2 · p. 10
- The coupon-collection lemma states a bound on the number of distinct coupons after N=cM draws, with δ>0.The proof reduces to δ∈(0,e^−c/2] and uses a harmonic-number approximation in bounding the draw count.Source: §6.2 · p. 11
- The proof bounds the probability of collecting a target number of distinct coupons by applying Chebyshev's inequality to the draw count T.It defines T as the number of draws needed to collect αM distinct coupons and uses bounds on its expectation and variance.Source: §6.2 · p. 11