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

Abstract

The problem of correcting deletions has recently received significantly increased attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a burst of at most two deletions in non-binary sequences. The problem was first studied for binary sequences by Levenshtein, who presented a construction with optimal redundancy. We propose a non-binary code correcting a burst of at most 2 deletions for q-ary alphabets with redundancy log n+O (log q log log n) bits, for even q. Further, we construct codes with lower redundancy to correct a burst of exactly 2 deletions caused by a single deletion in alternating sequences that arise in terminator-free enzymatic DNA synthesis.

Additional details