TY - JOUR
T1 - Bounds On the Maximum Cardinality of Indel and Substitution Correcting Codes
AU - Spee, Ward J. P.
AU - Weber, Jos H.
PY - 2024
Y1 - 2024
N2 - Recent advances in DNA data storage have attracted renewed attention towards deletion, insertion and substitution correcting codes. Compared to codes aimed at correcting either substitution errors or deletion and insertion (indel) errors, the understanding of codes that correct combinations of substitution and indel errors lags behind. In this paper, we focus on the maximal size of q-ary t-indel s-substitution correcting codes. Our main contributions include two Gilbert-Varshamov inspired lower bounds on this size. On the upper bound side, we prove a Singleton-like bound, a family of sphere-packing upper bounds and an integer linear programming bound. Several of these bounds are shown to improve upon existing results. Moreover, we use these bounds to derive a lower bound and an upper bound on the asymptotic redundancy of maximally sized t-indel s-substitution correcting codes.
AB - Recent advances in DNA data storage have attracted renewed attention towards deletion, insertion and substitution correcting codes. Compared to codes aimed at correcting either substitution errors or deletion and insertion (indel) errors, the understanding of codes that correct combinations of substitution and indel errors lags behind. In this paper, we focus on the maximal size of q-ary t-indel s-substitution correcting codes. Our main contributions include two Gilbert-Varshamov inspired lower bounds on this size. On the upper bound side, we prove a Singleton-like bound, a family of sphere-packing upper bounds and an integer linear programming bound. Several of these bounds are shown to improve upon existing results. Moreover, we use these bounds to derive a lower bound and an upper bound on the asymptotic redundancy of maximally sized t-indel s-substitution correcting codes.
KW - DNA data storage
KW - error correcting codes
KW - indels
KW - deletions
KW - insertions
KW - substitutions
KW - Gilbert-Varshamov bound
KW - Singleton bound
KW - sphere-packing bound
KW - ILP bound
UR - http://www.scopus.com/inward/record.url?scp=85190748525&partnerID=8YFLogxK
U2 - 10.1109/TMBMC.2024.3388971
DO - 10.1109/TMBMC.2024.3388971
M3 - Article
SN - 2332-7804
JO - IEEE Transactions on Molecular, Biological, and Multi-Scale Communications
JF - IEEE Transactions on Molecular, Biological, and Multi-Scale Communications
ER -