PaperlayerView exact revision on arXiv

Source-linked AI summary

Coding over Sets for DNA Storage

Andreas Lenz, Paul H. Siegel, Antonia Wachter-Zeh, Eitan Yaakobi

arXiv:1812.02936v3cs.ITmath.IT

TL;DR

DNA storage must handle unordered sets of sequences that may be lost or contain point errors. This paper models those errors, derives bounds, and proposes efficient code constructions; many constructions are reported as close to optimal.

  • Problem

    DNA storage codes must address both unordered strands and losses, insertions, deletions, and substitutions, with less known about correcting insertions and deletions than substitutions.

    Source: §I · p. 1

  • Method

    The paper models sequence losses and point errors, derives Gilbert–Varshamov lower bounds and sphere-packing upper bounds, and proposes explicit efficient code constructions.

    Source: B. DNA Channel Model · p. 3, §III · pp. 5–6, §VI · p. 18

  • Results

    Many proposed constructions are close to optimal, including for substitutions and single insertion or deletion errors inside all strands.

    Source: §VI · p. 18

  • Takeaways & Limitations

    The work establishes bounds and constructions for codes over sets in DNA storage, including constructions with full, reduced, or no indices.

    Source: §VI · p. 18

    The channel parameters s, t, and ǫ depend on the number of sequences drawn and the reconstruction algorithm.

    Source: C. Discussion of the Channel Model · p. 4

Abstract

from arXiv · show

In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of $M$ sequences, each of length $L$. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

I. INTRODUCTION

DNA storage uses unordered strands, making recovery difficult when strands are lost or contain insertion, deletion, or substitution errors. The paper develops a channel model for these errors and studies codes and bounds for reliable storage.

I. INTRODUCTION

  • Unordered strands make recovery challenging, while DNA errors include substitutions, insertions, and deletions; less is known about correcting insertions and deletions than substitutions.The paper targets the added difficulty of missing strand ordering.Source: §I · p. 1

A. Notation

  • The notation defines [n] as the natural numbers through n and distinguishes binary and DNA alphabets as Σ2 and Σ4.Vectors over a q-element alphabet are denoted by x ∈ Σq^n.Source: A. Notation · p. 2

B. DNA Channel Model

  • DNA storage is modeled as a set of M distinct length-L sequences, with s lost sequences, up to t erroneous sequences, and up to ǫ errors of type T in each erroneous sequence.The received set can contain between M − t − s and M distinct sequences because erroneous reconstructions may coincide with one another or with correct sequences.Source: B. DNA Channel Model · pp. 2–3

C. Discussion of the Channel Model

The paper models DNA storage as sets of sequences, where ordering is lost and sequences may be lost or received with errors. It derives Gilbert–Varshamov bounds for several error types and shows that deletion-correcting codes need not also correct insertions.

C. Discussion of the Channel Model

  • Set-based coding addresses lost sequence order and can handle loss or erroneous reception of stored sequences.The authors note that analyzing only a single-sequence channel cannot address the set-level problem of whether prepending indices is optimal when some sequences arrive correctly.Source: C. Discussion of the Channel Model · p. 4

D. Relationship of Insertion- and Deletion-Correcting Codes

  • Deletion-correcting codes do not necessarily correct insertions, and the converse implication also fails in this channel model.The authors give a counterexample for the deletion-to-insertion direction and state that the reverse counterexample can be constructed analogously.Source: D. Relationship of Insertion- and… · p. 4

III. GILBERT-VARSHAMOV BOUNDS

  • The generalized Gilbert–Varshamov results establish code-existence bounds for arbitrary per-sequence errors, substitutions, and deletions.The deletion-bound derivation accounts for the non-uniform size of deletion spheres.Source: §III · pp. 5–6
  • For fixed s, t, and 0 < β < 1, the redundancy bound is r(C) ≤ (s + 2t)L + (s + 2t) log M − log((s + 2t)!2) + o(1).The passage states this result for an (s, t, •)L-correcting code.Source: §III · p. 5
  • Table II summarizes lower and upper redundancy bounds for optimal (s, t, ǫ)T-correcting codes, with low-order terms omitted.The caption identifies the table’s scope but does not provide the bound values.Source: Table II · p. 6

IV. SPHERE-PACKING BOUNDS

The sphere-packing analysis bounds code sizes from above, but input-dependent error-ball sizes make direct bounds difficult. The paper uses upper bounds on error-ball size and an asymptotic analysis to obtain tractable bounds, which are asymptotically tight for many channel parameters.

IV. SPHERE-PACKING BOUNDS

  • The sphere-packing bound supplies upper bounds on code cardinality and thereby lower bounds on redundancy.The paper derives these bounds for the (s, t, ε)T-correcting codes of its DNA storage channel.Source: §IV · p. 7
  • Because error-ball sizes depend on the channel input, generalized sphere packing does not yield tractable expressions for this channel.The paper instead upper-bounds error-ball size and uses an asymptotic analysis in which most error balls have similar sizes for large M.Source: §IV · p. 7
  • The sphere-packing bounds are asymptotically tight for many channel parameters when considered alongside the Gilbert-Varshamov bounds and concrete code constructions.They also provide insights into the nature of the DNA channel.Source: §IV · p. 7

A. Non-Asymptotic Bounds

The section derives non-asymptotic sphere-packing bounds for sequence loss and insertion errors, then gives asymptotic redundancy bounds and interprets the extra cost of erroneous sequences. For deletion errors, a conservative bound based on the minimum deletion-ball size is weak.

A. Non-Asymptotic Bounds

  • r(C) ≥ (s+t) log(2L−M−t) + t log(M−s−t) − log(t!(s+t)!) for any (s, t, •)L-correcting code.This is the section’s non-asymptotic lower bound on redundancy.Source: A. Non-Asymptotic Bounds · p. 7
  • For fixed s and t, r(C) ≥ (s+t)L + t log M − log(t!(s+t)!) + o(1) as M → ∞ with M = 2^βL.The asymptotic bound holds for fixed 0 < β < 1.Source: A. Non-Asymptotic Bounds · pp. 7–8
  • Erroneous sequences require roughly log M more redundancy than lost sequences because they cannot be directly detected by the decoder.When losses and erroneous sequences both scale with M, the redundancy depends only on σ + τ.Source: A. Non-Asymptotic Bounds · p. 8
  • The section also derives a sphere-packing upper bound on code cardinality for codes correcting s lost sequences and ε insertions in each of t sequences.The proof lower-bounds the error-ball size by counting distinct received sets formed from error-free and erroneous sequences.Source: A. Non-Asymptotic Bounds · p. 8
  • For deletion errors, a conservative bound based on the minimum deletion-ball size is weak because that minimum is ε + 1.The text points to an asymptotic analysis for tighter bounds.Source: A. Non-Asymptotic Bounds · p. 8

B. Asymptotic Bounds for Substitution Errors

The section derives asymptotic sphere-packing bounds for substitution errors by lower-bounding error-ball sizes and separating sets that contain large substitution-correcting codes. The bounds cover both fixed numbers of errors and a number of erroneous sequences that scales with M.

Theorem 7

  • Theorem 7 bounds the error-ball size using an ε-substitution-correcting code contained in the stored set and counts choices of lost and erroneous sequences.The proof then bounds the contribution of sets lacking a large such code and shows it is asymptotically negligible.Source: B. Asymptotic Bounds for Substitution… · pp. 8–10
  • The proof lower-bounds an error ball by counting distinct outputs from sequence losses and substitution patterns, choosing outcomes so different error realizations remain distinguishable.The construction uses an ε-substitution-correcting code to ensure selected erroneous outcomes do not occur in other codeword error balls.Source: B. Asymptotic Bounds for Substitution… · pp. 8–9
  • For fixed s, t, and ε, the redundancy lower bound includes sL, t log M, and tε log L terms, up to the stated asymptotic terms.The section notes that for s = 0 and ε = 1, the bound is t log(ML) − log t! bits.Source: B. Asymptotic Bounds for Substitution… · pp. 10–11
  • For the (0,t,1)_S channel, redundancy is intuitively at least t log(ML) − log t! bits for t errors among ML symbols; sphere-packing comparison suggests unordered sequences require as much redundancy as an ordered array with unknown error distribution.Source: B. Asymptotic Bounds for Substitution… · p. 11

Theorem 8

  • For M = 2^βL and a number of erroneous sequences scaling with M, the section derives a separate asymptotic sphere-packing bound.The theorem treats fixed s and ε while the number of erroneous sequences is M − s.Source: B. Asymptotic Bounds for Substitution… · p. 11

C. Asymptotic Bounds for Deletion Errors

The section derives sphere-packing bounds for deletion errors, accounting for nonuniform deletion-ball sizes through properties of typical sequences. It compares the resulting redundancy with substitution-error bounds and also treats a number of erroneous sequences that scales with M.

Theorem 9

  • The deletion-bound argument uses that most deletion balls have similar sizes, despite the balls being nonuniform.It focuses on sets with large deletion-correcting subsets and sequences having at least L/2 − ρ(L) runs.Source: C. Asymptotic Bounds for Deletion Errors · pp. 11–12
  • Theorem 9 gives a sphere-packing bound for fixed s, t, and ε, with the relevant sets containing more than M − y(M) sequences meeting the stated run threshold.Here y(M) is chosen as M / log M.Source: C. Asymptotic Bounds for Deletion Errors · p. 12
  • For fixed s, t, and ε, substitution errors require t log M − log t! more redundancy than insertion or deletion errors.The section explains that deletion strands can be identified by their length, whereas substitution-corrupted strands can be confused with correct ones.Source: C. Asymptotic Bounds for Deletion Errors · p. 12

Theorem 10

V. CODE CONSTRUCTIONS

The construction section frames DNA-storage coding as a joint challenge of unordered sequence reception and errors within sequences. It motivates codes that distribute redundancy across strands rather than relying only on per-strand protection.

V. CODE CONSTRUCTIONS

  • Efficient constructions must address both the loss of sequence ordering and random errors within sequences.The paper states that concatenated inner- and outer-code schemes are suboptimal when only a few sequences contain errors, because correct sequences do not need the inner code.Source: §V · p. 13
  • The proposed design direction is to protect the set of strands collectively, using redundancy across sequences to correct errors in a subset.The section says specialized constructions for different error types and parameter choices follow.Source: §V · p. 13
  • The section begins with constructions for arbitrary numbers of errors per sequence and reserves more specialized constructions for later.Source: §V · p. 13

A. Indexing Sequences

Indexing restores sequence positions by prepending an index to each strand, but incurs redundancy proportional to the number of sequences. The section also notes that indexing is capacity achieving when there are no errors inside sequences.

A. Indexing Sequences

B. An Index-Based Construction using MDS Codes

Construction 1 prepends an index to each sequence and protects the remaining symbols with an MDS code, allowing decoding of sequence losses and several kinds of sequence errors. Its correction conditions depend on whether errors can be detected by their sequence lengths.

B. An Index-Based Construction using MDS Codes

  • Construction 1 indexes each sequence and applies an MDS code across the remaining symbols, enabling standard MDS encoders and decoders.The construction does not require a specific split between losses and errors; its decoding condition uses their combined redundancy requirement.Source: B. An Index-Based Construction using… · pp. 14–15
  • For deletion-only errors, the code corrects s losses and t erroneous sequences when s + t ≤ δ.Sequences with lengths different from L can be discarded and treated as erasures.Source: B. An Index-Based Construction using… · p. 14
  • The proof bounds the received MDS word by s′ + 2t′ ≤ s + 2t ≤ δ, accounting for erroneous sequences that collide with existing indices.Erroneous sequences with repeated indices can turn positions into erasures rather than errors.Source: B. An Index-Based Construction using… · p. 14
  • With losses and substitution-plus-deletion or substitution-plus-insertion errors, correction is guaranteed when s + 2tS + tD ≤ δ.For mixtures of substitutions, insertions, and deletions, sequences whose final length is L may be undetectable by length, requiring s + 2t ≤ δ.Source: B. An Index-Based Construction using… · p. 14
  • The MDS portion adds δ(L − ⌈log M⌉) redundancy bits, in addition to the redundancy needed for indexing.The paper notes that total redundancy can be very large, especially when M ≫ L.Source: B. An Index-Based Construction using… · pp. 14–15

C. A Construction Based On Constant Weight Codes

Construction 2 represents each unordered sequence set as a constant-weight binary vector, then uses codes that correct losses and errors in that representation. The resulting redundancy is at most (s + 2t)L, but efficient encoding and decoding are unclear.

C. A Construction Based On Constant Weight Codes

  • Each sequence set maps to a length-2L constant-weight binary vector, with a 1 marking each sequence present in the set.A loss becomes a 1 → 0 error, while a sequence substitution becomes an error in the Johnson graph.Source: C. A Construction Based On Constant… · p. 15
  • Construction 2 corrects s sequence losses and errors in t sequences using a code that handles asymmetric errors and errors in the Johnson graph.The construction maps a suitable constant-weight codeword back to its corresponding sequence set.Source: C. A Construction Based On Constant… · p. 15
  • Redundancy is at most (s + 2t)L for Construction 2.The proof represents each loss by one substitution error and each sequence error by at most two.Source: C. A Construction Based On Constant… · p. 15
  • Construction 2 has lower redundancy than Construction 1, especially when M = 2^βL, but efficient encoding and decoding are unclear.The constant-weight code has length exponential in L, and the unordered set lacks an inherent ordering.Source: C. A Construction Based On Constant… · p. 16

D. An Improved Indexed-Based Construction

Construction 3 reduces indexing redundancy by assigning shared prefix indices to groups of sequences and protecting the groups with an MDS code. Its parameter c trades off indexing and MDS redundancy.

D. An Improved Indexed-Based Construction

  • Construction 3 reduces the bits used to index each sequence, trading redundancy as a function of L and M.It groups sequences sharing the c log M most significant index bits, with M^c groups of M^(1−c) sequences each.Source: D. An Improved Indexed-Based… · p. 16
  • Construction 3 corrects losses and erroneous sequences when s + 2t ≤ δ.Its grouped-index decoder identifies affected groups as erasures when their sizes reveal an error.Source: D. An Improved Indexed-Based… · p. 16
  • For insertion-only or deletion-only errors, sequences of abnormal length can be discarded, leaving at most s + t erasures in the MDS code.These erasures are correctable when s + t ≤ δ.Source: D. An Improved Indexed-Based… · p. 16
  • For fixed 0 < c < 1, the indexing terms scale as M^c, while the MDS redundancy term scales as M^(1−c).Thus indexing dominates asymptotically for c > 0.5, and MDS redundancy dominates for c < 0.5.Source: D. An Improved Indexed-Based… · p. 16

E. Concatenated Constructions

The paper describes concatenated codes that separate within-sequence correction from sequence-loss correction, then presents specialized constructions for insertion, deletion, and substitution errors. The special constructions include single insertion/deletion guarantees and asymptotically optimal or near-optimal redundancy claims.

E. Concatenated Constructions

  • An outer code over sequence sets can be concatenated with an inner block code to address both sequence losses and errors within sequences.The inner code corrects errors within sequences; the outer code then corrects lost sequences.Source: E. Concatenated Constructions · p. 17
  • If the inner code corrects ε errors of type T and the outer code handles s losses, the concatenated construction corrects (s, M − s, ε) errors of type T.The authors note that outer codes such as Constructions 1, 2, or 3 can also correct losses when s + 2t ≤ δ.Source: E. Concatenated Constructions · p. 17

F. Special Constructions

  • Construction 5 uses checksums and a single-erasure-correcting code to recover the checksum of one distorted sequence, then correct its insertion or deletion.The checksum deficiency is computed modulo L + 1, and the sequence is corrected with a Varshamov-Tenengolts code.Source: F. Special Constructions · p. 17
  • For all M, L, and a, C5(M, L, a) is an (0, 1, 1)ID-correcting code, with redundancy r(C5(M, L, a)) ≤ log(L + 1).Source: F. Special Constructions · p. 17
  • Construction 6 uses a shared Varshamov-Tenengolts checksum to correct one insertion or deletion in each sequence.The paper states its redundancy is asymptotically optimal in scaling with M and L.Source: F. Special Constructions · pp. 17–18
  • Construction 7, represented by C7(M, L, ε), is an (0, M, ε)S-correcting code that can correct ε substitution errors in each sequence.For fixed ε, this construction is close to optimality.Source: F. Special Constructions · p. 18

VI. CONCLUSION

The paper develops bounds and constructions for error-correcting codes over sets in DNA storage, including constructions for sequence losses combined with within-sequence errors. Many constructions are close to optimal for specified error cases, and the bounds reveal that insertions or deletions require less redundancy than substitutions.

VI. CONCLUSION

  • Many proposed constructions are close to optimal for substitutions and single insertion or deletion errors inside all strands.The paper also compares construction sizes with sphere-packing bounds.Source: §VI · p. 18
  • The paper extends Gilbert–Varshamov lower bounds and sphere-packing upper bounds and proposes constructions with full, reduced, or no indices.It also gives special constructions for particular parameter choices.Source: §VI · p. 18
  • The constructions also address combinations of sequence loss and within-sequence errors; the bounds indicate that insertions or deletions require less redundancy than substitutions.Source: §VI · p. 18

APPENDIX A AUXILIARY LEMMAS

Appendix A presents auxiliary asymptotic estimates, including bounds involving logarithms and binomial coefficients under stated growth conditions. Appendix B uses group cardinalities and Stirling’s approximation to derive redundancy for Construction 3, with a stated special case when c = 1.

APPENDIX A AUXILIARY LEMMAS

  • For f(n)=o(1), an auxiliary estimate uses logarithmic bounds and a first-order approximation involving g(n) ln(1+f(n)).The proof invokes the standard natural-logarithm bound for x > −1.Source: Appendix A · pp. 18–19
  • A binomial-coefficient estimate is stated for g(n)=o(f(n)) and g(n)=ω(1), with its proof using a refinement of Stirling’s approximation.Source: Appendix A · pp. 18–19
  • Another asymptotic property is stated for fixed δ, y(M)≤M, and z(L)≤2L/y(M) for sufficiently large M, in the regime M=2^βL with 0<β<1.The proof is described as a direct binomial-coefficient calculation.Source: Appendix A · p. 19

APPENDIX B PROOF OF THEOREM 14

  • For Construction 3, the groups contain M^(1−c) unordered distinct sequences, with M^(c−δ) information groups and δ MDS redundancy groups.The redundancy calculation uses Stirling’s approximation; for c = 1, it yields the same redundancy as Theorem 12.Source: Appendix B · p. 19

Related papers

Loading 1812.02936v3…