Duplication-correcting codes

Andreas Lenz, Antonia Wachter-Zeh, Eitan Yaakobi

Abstract

DNA-based data storage offers unprecedented density and longevity, yet it is susceptible to unique biological error patterns, specifically tandem and palindromic duplications. This paper explores the development of specialized error-correcting codes designed to mitigate these errors more efficiently than traditional burst-error correction methods. By leveraging mathematical properties such as the equivalence between duplication and deletion correction and employing hypergraph theory for bound estimation, the authors propose new code constructions that significantly reduce redundancy while maintaining high data rates.

Introduction

As the global demand for data storage scales exponentially, DNA has emerged as a promising medium due to its biological stability and massive information density. However, the transition from silicon to synthetic or biological DNA storage introduces novel noise profiles. Unlike traditional magnetic or solid-state drives, which primarily suffer from bit-flips, DNA storage is prone to insertion and deletion errors, particularly duplications occurring during replication or synthesis.

Duplication errors typically manifest in two forms:

  1. Tandem Duplications: A segment of the sequence is repeated immediately following its original occurrence (e.g., GATCATG becomes GATCATCATG).
  2. Palindromic Duplications: A segment is repeated in its reverse order (e.g., GATCATG becomes GATCCTAATG).

While general-purpose "burst insertion" codes can address these errors, they are often suboptimal because they assume any arbitrary sequence can be inserted. By exploiting the structural constraints of duplications—where the inserted sequence is a copy of existing data—researchers can design leaner, more efficient codes.

Notation and Definitions

To rigorously analyze these error models, the authors establish a formal notation for various operations and sequence representations. These definitions form the mathematical foundation for the proposed correction algorithms.

Table of notation and definitions for duplication and deletion operations, error spheres, and sequence representations.

The notation includes operators for tandem ($\tau_\ell$) and palindromic ($\rho_\ell$) duplications and deletions, as well as the concepts of "$\ell$-trunks" ($\mu_\ell$) and "$\ell$-zero signatures" ($\sigma_\ell$), which are pivotal for the proposed code constructions.

Methodology

The research approaches the problem through a combination of theoretical proofs and algorithmic construction.

The Equivalence Proof

A foundational contribution of this work is the proof that a code capable of correcting $t$ tandem duplications is functionally equivalent to one that corrects $t$ tandem deletions. This mathematical symmetry allows researchers to adapt well-established tools from deletion-correcting theory to the duplication problem, simplifying the search for optimal codes.

Hypergraph Transversals and Sphere Packing

To determine the theoretical limits of data density (the Sphere Packing Bound), the authors utilized hypergraph theory. By modeling possible errors as edges within a hypergraph, they sought a "transversal" (a set of codewords that avoids overlapping error balls) to establish non-asymptotic upper bounds on code size. This provides a benchmark for evaluating the efficiency of practical implementations.

Specialized Code Constructions

The authors introduced two primary classes of codes:

  • Tandem Error Correction: By mapping the problem to the $\ell_1$-metric, the authors adapted Varshamov-Tenegolts (VT) codes. These codes utilize a checksum-based approach to handle the specific "signature" left by tandem repeats.
  • Palindromic Error Correction: Correcting palindromic errors is inherently more complex due to the increased ambiguity of reversed sequences. The authors proposed codes incorporating "run-length profile" constraints and specific checksums to pinpoint the location of reversed repeats. For scenarios where the duplication length is unknown, a "palindrome-free" construction was developed.

Key Insights

A significant finding is the disparity in difficulty between correcting tandem versus palindromic duplications. Palindromic errors require substantially more redundancy because the reversed sequence can blend into the original strand in more ambiguous ways than a direct repeat.

Furthermore, the "Trunk and Signature" technique proved highly effective. By representing a sequence by its $\ell$-trunk (the base sequence with repeats removed) and its $\ell$-zero signature (a record of repeat counts), the complex problem of duplication correction is reduced to a more manageable combinatorial task.

Results and Performance

The proposed codes demonstrate clear advantages over general-purpose alternatives:

  • Redundancy Efficiency: For a single palindromic duplication of length 2, the new code achieves a redundancy of approximately $\log_2(n) + \log_2(10)$. This outperforms standard burst-insertion codes, which typically require an additional $\log_2(\log_2(n))$ term.
  • Asymptotic Rate: For "palindrome-free" codes, the code rate (the ratio of information bits to total bits) approaches 1 as the alphabet size increases, indicating high efficiency for large-scale DNA storage.
  • Tightened Bounds: The work provides the first non-asymptotic upper bounds for these specific error types, offering a theoretical "speed limit" for future code designs.

Limitations and Future Directions

While the current constructions are optimized for single duplication errors, real-world biological environments often involve multiple simultaneous errors. Future research should focus on:

  1. Multiple Duplications: Extending the current framework to handle strands with two or more duplications.
  2. Hybrid Error Models: Developing codes robust against a mix of duplications, deletions, and substitutions (bit-flips).
  3. Refining Palindromic Bounds: Closing the remaining gap between theoretical limits and practical code performance for palindromic errors.

By tailoring error correction to the specific biological realities of DNA, this research paves the way for more reliable and efficient molecular data storage systems.

Summary updated

Abstract

In this work, we propose constructions that correct duplications of multiple consecutive symbols. These errors are known as tandem duplications, where a sequence of symbols is repeated; respectively as palindromic duplications, where a sequence is repeated in reversed order. We compare the redundancies of these constructions with code size upper bounds that are obtained from sphere packing arguments. Proving that an upper bound on the code cardinality for tandem deletions is also an upper bound for inserting tandem duplications, we derive the bounds based on this special tandem deletion error as this results in tighter bounds. Our upper bounds on the cardinality directly imply lower bounds on the redundancy which we compare with the redundancy of the best known construction correcting arbitrary burst insertions. Our results indicate that the correction of palindromic duplications requires more redundancy than the correction of tandem duplications and both significantly less than arbitrary burst insertions.
BibTeX
@article{lenz2019duplication,
  author = {Andreas Lenz and Antonia Wachter-Zeh and Eitan Yaakobi},
  title = {{Duplication-correcting codes}},
  journal = {Des. Codes Cryptogr.},
  year = {2019},
  doi = {10.1007/s10623-018-0523-0},
}
Figure