Combinatorial alphabet-dependent bounds for insdel codes
Preprint
Abstract
Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. Due to their important applications in DNA storage and computational biology, insdel codes have recently become a focal point of research in coding theory. In this paper, we present several new combinatorial upper and lower bounds on the maximum size of $q$-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distance $d$ or the alphabet size $q$ is large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block length $n$ and edit distance $d$, when $q$ is sufficiently large, the maximum size of insdel codes is $ \frac{q^{n-\frac{d}{2}+1}}{{n\choose \frac{d}{2}-1}}(1 \pm o(1))$. The second lower bound refines Alon et al.'s recent logarithmic improvement on Levenshtein's GV-type bound and extends its applicability to large $q$ and $d$.
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- A Characterization of the DNA Data Storage ChannelScientific Reports, 2019
- Portable and Error-Free DNA-Based Data StorageScientific Reports, 2017
- On multiple insertion/deletion correcting codesIEEE Transactions on Information Theory, 2002
- A Combinatorial Construction for Perfect Deletion-Correcting CodesDesigns, Codes and Cryptography, 2001
- Efficient Reconstruction of Sequences from Their Subsequences or SupersequencesJournal of Combinatorial Theory, Series A, 2001
- A linear programming perspective on the Frankl?R dl?Pippenger theoremRandom Structures & Algorithms, 1996
- On the construction of perfect deletion-correcting codes using design theoryDesigns, Codes and Cryptography, 1995
- A note on Ramsey numbersJournal of Combinatorial Theory, Series A, 1980
- Some general results of coding theory with applications to the study of codes for the correction of synchronization errorsInformation and Control, 1969
- Elementary Matrix AlgebraPhysics Today, 1960