Non-binary Codes for Correcting a Burst of at Most t Deletions

Shuche Wang, Yuanyuan Tang, Jin Sima, Ryan Gabrys, Farzad Farnoud

TL;DR

This paper introduces new non-binary codes designed to correct "bursts" of deletions in data, particularly relevant for emerging DNA data storage. The authors present codes that are more efficient (require fewer redundant bits) than previous methods for correcting these deletion errors, especially for larger alphabets and longer deletion bursts.

What Problem Does This Paper Address?

Storing data in DNA is promising due to its high density, but it's prone to errors, especially consecutive insertions and deletions (bursts). Correcting these "bursts" of deletions in non-binary sequences (sequences using an alphabet larger than just 0 and 1) is a significant challenge. Existing methods often require a lot of redundant information, making them inefficient. This paper aims to develop more efficient non-binary codes that can correct consecutive deletions of a certain length, with a focus on minimizing the overhead (redundancy). They also extend this to correcting deletions in permutations, which are relevant for certain DNA synthesis methods.

Methods

The authors employ a multi-pronged approach:

  • Mapping to Binary: They convert non-binary sequences into binary matrices. This allows them to leverage existing techniques for binary error correction.
  • Levenshtein Code Adaptation: They build upon the well-known Levenshtein code for binary sequences, providing a simpler proof and adapting it for non-binary sequences and specific error patterns.
  • Pattern Length Limited (PLL) Codes: To handle the ambiguity in locating deletions, they introduce "pattern length limited" codes. These codes ensure that specific patterns within the encoded sequence have a limited length, which helps narrow down the possible error locations.
  • P-Bounded Codes: For correcting deletions when the location is approximately known, they develop "P-bounded" codes. These codes use syndromes and parity constraints to pinpoint errors within a defined range.
  • Permutation Encoding: For permutation-based data, they use a mapping to binary sequences and then apply densifying techniques and overlapping ranking sequences to locate and correct deletions.

Datasets

Not discussed in the paper. The paper focuses on theoretical code construction and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • DNA Storage Motivation: The prevalence of insertion/deletion errors in DNA data storage is a strong motivator for this research, highlighting the practical importance of these codes.
  • Efficiency Gains: The proposed codes achieve significantly lower redundancy compared to prior art, especially for larger alphabets and longer deletion bursts, making them more practical for real-world applications.
  • Bridging Binary and Non-Binary: The strategy of mapping non-binary sequences to binary matrices is a powerful technique that allows leveraging established binary coding theory for more complex non-binary problems.
  • Handling Ambiguity: The introduction of "pattern length limited" and "densifying" techniques is crucial for dealing with the inherent ambiguity in locating deletion errors, a common challenge in burst error correction.
  • Permutation Codes for DNA: The extension to permutation codes addresses specific challenges in DNA synthesis where sequences might be represented as permutations.

Key Results

  • Non-Binary Codes for t=2 Deletions: For even alphabet sizes $q$, they construct non-binary codes that correct a burst of at most 2 deletions with redundancy $O(\log n + \log q \log \log n)$.
  • Non-Binary Codes for General t Deletions: They extend this to correct bursts of at most $t$ deletions with redundancy $O(\log n + \log q \log \log n)$.
  • Permutation Codes: They propose permutation codes that can correct a burst of at most $t$ deletions with redundancy $O(\log n + \log \log n)$.
  • Near-Optimal Redundancy: The paper claims that the proposed codes are the largest known for their respective parameter regimes, meaning they achieve near-optimal redundancy.

Limitations and Future Work

  • Systematic Codes: The paper acknowledges that the presented codes are non-systematic. Developing systematic encoding schemes for low-redundancy non-binary burst-error-correcting codes remains an open problem.
  • Codes Correcting Bursts of Edits: The current work focuses on deletions. Future research could explore codes that correct bursts of insertions, deletions, and substitutions simultaneously, which have applications beyond DNA storage, such as in document exchange.
  • Multiple Bursts: The problem of correcting multiple bursts of deletions (or other edits) is also highlighted as an area for future investigation.
  • Even Alphabet Size: Some constructions are specifically for even alphabet sizes $q$. Extending these to odd $q$ could be a direction for future work.

Summary updated

Abstract

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most $t$ deletions in non-binary sequences. We first propose a non-binary code correcting a burst of at most 2 deletions for $q$-ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most $t$ where $t$ is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.
BibTeX
@article{wang2022non,
  author = {Shuche Wang and Yuanyuan Tang and Jin Sima and Ryan Gabrys and Farzad Farnoud},
  title = {{Non-binary Codes for Correcting a Burst of at Most t Deletions}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=LvuLvYmaUq},
}
Figure