Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms

I. INTRODUCTION

• Mutations including tandem duplications, point mutations, insertions, and deletions threaten stored information, with deleterious events accumulating over generations.Source: §I · p. 1
• Earlier live-DNA encodings were generally not designed for tandem duplications; repetition coding can correct them but has high redundancy.Source: §I · pp. 1–2
• The paper constructs codes for fixed-length duplications that correct any number of errors and are optimal in size.A mapping makes length-k duplications equivalent to inserting k zeros, connecting the codes to Run-Length Limited systems.Source: §I · p. 2
• For a bounded number of fixed-length duplication errors, the paper relates codes to constant-weight codes in the ℓ1 metric.Source: §I · p. 2
• For duplications of length at most 2 or 3, the paper constructs codes that correct any number of errors; the length-at-most-2 codes are optimal.Source: §I · p. 2
• The paper fully classifies the parameters for which allowed duplication lengths give every sequence a unique root.The number of roots depends on the allowed duplication lengths and alphabet size.Source: §I · p. 2

II. PRELIMINARIES

• Σ denotes a finite alphabet, Σ* its finite words, and Preft and Sufft the first and last t symbols of a word.Source: §II · p. 2
• A length-k tandem duplication copies a contiguous substring next to itself; a descendant is reachable through a finite sequence of such duplications.Source: §II · pp. 2–3
• Deduplication removes one copy of an adjacent repeated substring, and roots are ancestors that cannot be deduplicated further.Source: §II · p. 4
• An (n,M;t)_k code is defined for the fixed-length-k channel, with t denoting the number of errors it corrects.The notation also allows t = * for correction of all errors.Source: §II · p. 4

Transform and unique roots

• Under the φk transform, length-k duplication inserts k consecutive zeros, and repeated deduplication yields the unique root by reducing zero-run lengths modulo k.The transform also characterizes irreducible words by requiring the transformed suffix to contain no k consecutive zeros.Source: §III · pp. 6–7
• Two words are k-congruent exactly when their φk transforms have the same first k symbols and their suffixes have the same reduced zero-run signature.The reduced signature together with µk uniquely determines a string.Source: §III · pp. 6–7

Construction A

• Construction A yields an optimal code correcting any number of length-k tandem duplications, with one codeword from each k-congruence class.Its codewords are built from irreducible words with k consecutive zeros appended; distinct codewords have disjoint descendant cones.Source: §III · p. 8
• The code family’s asymptotic rate equals the capacity of the q-ary (0,k−1)-RLL constrained system.The constraint consists of strings with no k consecutive zeros.Source: §III · pp. 7–8

Bounded-error codes

• For bounded-error codes, the section defines a distance among k-congruent words and states that correction of t duplications is equivalent to an ℓ1 constant-weight code with distance at least t+1.The criterion applies to zero signatures of the transformed suffixes of k-congruent codewords.Source: §III · pp. 9–10

III. k-TANDEM-DUPLICATION CODES

• C is an (n, M; t)k code exactly when each associated C(y, z) is a constant-weight code with minimum ℓ1-distance t + 1.The associated codes have parameters (n(y, z), M(y, z)).Source: §III · p. 10
• Construction B fixes Σ = Zq, k ≥ 1, n ≥ k, and t ≥ 0, and uses length-m codes of constant ℓ1-weight w and minimum ℓ1-distance t + 1 to construct an (n, M; t)k code.Source: §III · p. 11
• Optimal ℓ1-metric codes in Construction B would yield optimal (n, M; t)k codes, but explicit constructions are unavailable.The authors suggest deriving them from Lee-metric codes such as and using averaging to infer constant-weight codes, leaving construction for future work.Source: §III · p. 11

• For duplications of length ≤2, the paper gives optimal codes and exact channel capacity; for length ≤3, it constructs codes correcting any number of errors and gives a capacity lower bound.Source: §IV · p. 11
• Every sequence has a unique root under duplication lengths ≤3, and thus also ≤2 or 1; this property is used in code construction.Source: §IV · pp. 11–12
• Construction C selects one representative per ≤3 equivalence class, yielding a code whose codewords have disjoint descendant cones and correct all such errors.Source: §IV · p. 13
• The ≤3-irreducible words form a regular language represented by a finite labeled graph, which enables calculation of its capacity.Source: §IV · p. 13
• Construction D selects one codeword from each ≤2 equivalence class, making the resulting code optimal.Source: §IV · p. 15

• For a one-symbol alphabet, the pair is unique-root exactly when the minimum allowed length divides every allowed duplication length.Source: §V · p. 16
• For alphabets of size at least 3, adding any nonempty set of lengths greater than 3 to either {1, 2} or {1, 2, 3} produces a non-unique-root pair.Source: §V · p. 17
• The classification makes unique-root status depend on the alphabet and allowed duplication lengths; fixed-length and length-at-most-3 channels are identified as unique-root cases.Source: §V · pp. 15, 17
• For a binary alphabet, allowing both duplication lengths 1 and 2 gives a unique root for every sequence, regardless of other allowed lengths.Source: §V · p. 17
• For alphabets of size at least 3, allowed lengths {1, 2} and {1, 2, 3} each give the unique-root property.Source: §V · p. 17

VI. CONCLUSION

• The codes mostly rely on pairs of alphabets and duplication lengths with unique roots.Source: §VI · p. 18
• Constructing general (n, M; ∗)U codes over Σ remains open, especially without unique roots.Source: §VI · p. 18
• Counting a string’s distinct roots and finding strings of a given length with as many roots as possible remain open combinatorial problems.Source: §VI · p. 18

APPENDIX

• The proof estimates the largest eigenvalue of Aq(k) by estimating the largest root of its characteristic polynomial.Source: APPENDIX · p. 18
• The function f(x) is decreasing and then increasing across stated intervals, placing its unique largest root within a range.Source: APPENDIX · p. 19
• The parameter α depends on q and k, satisfies α = 1 + o(1) as k → ∞, and is at least 1 for the stated parameter cases.The Lambert W function is valid for all parameter values except k = 1 and q = 2.Source: APPENDIX · p. 19