Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems

Abstract

A (tandem) duplication of length $k$ is an insertion of an exact copy of a substring of length $k$ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein's construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length $k$. Furthermore, we derive bounds on the cardinality of optimal $q$-ary codes correcting up to $t$ duplications of length $k$, and establish the following corollaries in the asymptotic regime of growing block-length: 1.) the presented family of codes is optimal for every $q,t,k$, in the sense of the asymptotic scaling of code redundancy; 2.) the upper bound, when specialized to $q=2$, $k=1$, improves upon Levenshtein's bound for every $t\ge 3$; 3.) the bounds coincide for $t=1$, thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes.

arXiv commentTo appear in IEEE Communications Letters

References in corpus (4)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms
• Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
• Error correcting codes and B_h-sequences

Cited by in corpus (16)

• Coding Theorems for Noisy Permutation Channels
• Reconstruction Codes for DNA Sequences with Uniform Tandem-Duplication Errors
• On Conflict Free DNA Codes
• Single-Error Detection and Correction for Duplication and Substitution Channels
• Zero-Error Capacity of Duplication Channels
• Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
• Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences
• Permutation Capacity Region of Adder Multiple-Access Channels
• Uncertainty of Reconstruction with List-Decoding from Uniform-Tandem-Duplication Noise
• On the Maximum Number of Non-Confusable Strings Evolving Under Short Tandem Duplications
• Evaluation of the Gilbert-Varshamov Bound using Multivariate Analytic Combinatorics
• Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics
• Optimal codes with small constant weight in ${\ell }_1$-metric
• Error-correcting Codes for Noisy Duplication Channels
• Optimal Ternary Codes with Weight $w$ and Distance $2w-2$ in ${\ell }_1$-Metric
• Error-correcting Codes for Short Tandem Duplication and Substitution Errors