Abstract
We find a method for constructing DNA codes with single-deletion-correcting capability. We first present an explicit algorithm for the construction of the q-ary single-deletion-correcting codes (abbreviated as SDC codes) using a class of the complementary information set codes (abbreviated as CIS codes), where q is a power of a prime. We then show that the encoding/decoding scheme of the CIS codes with single-deletion-correcting capability has a simple deterministic algorithm. Finally, applying our algorithm to the generated DNA codes with appropriate modification, we obtain the DNA codes with single-deletion-correcting capability. We present some various examples of such DNA codes, and we also obtain some lower bounds on the maximum size of the single-deletion-correcting DNA codes.
Similar content being viewed by others
References
Abdel-Ghaffar K.A., Ferreira H.C., Cheng L.: Correcting deletions using linear and cyclic codes. IEEE Trans. Inform. Theory 56(10), 5223–5234 (2010).
Aboluion N., Smith D.H., Perkins S.: Linear and nonlinear constructions of DNA codes with Hamming distance \(d\), constant GC-content and a reverse-complement constraint. Discret. Math. 312(5), 1062–1075 (2012).
Baker S., Flack R., Houghten S.: Optimal variable-length insertion-deletion correcting codes and edit metric codes. Congr. Numer. 186, 65–80 (2007).
Blawat M., et al.: Forward error correction for DNA data storage. Proc. Comput. Sci. 80, 1011–1022 (2016).
Cannon J., Playoust C.: An Introduction to Magma. University of Sydney, Sydney (1994).
Carlet C., Gaborit P., Kim J.-L., Solé P.: A new class of codes for Boolean masking of cryptographic computations. IEEE Trans. Inform. Theory 58, 6000–6011 (2012).
Gaborit P., King O.D.: Linear constructions for DNA codes. Theor. Comput. Sci. 334(1–3), 99–113 (2005).
Gabrys R., Yaakobi E., Milenkovic O.: Codes in the Damerau distance for deletion and adjacent transposition correction. IEEE Trans. Inform. Theory 64(4), 2550–2570 (2018).
Jain S., et al.: Duplication-correcting codes for data storage in the DNA of living organisms. IEEE Trans. Inform. Theory 63(8), 4996–5010 (2017).
Kim H.J., Choi W.-H., Lee Y.: Designing DNA codes from reversible self-dual codes over \(GF(4)\). preprint.
Kim H.J., Choi W.-H., Lee Y.: Construction of reversible self-dual codes. Finite Fields Appl. (2020). https://doi.org/10.1016/j.ffa.2020.101714.
Kim H.J., Lee Y.: Complementary information set codes over \(GF(p)\). Des. Codes Cryptogr. 81, 541–555 (2016).
King O.D.: Bounds for DNA codes with constant GC-content. Electron. J. Comb. 10, R33 (2003).
Kulkarni A.A., Kiyavash N., Sreenivas R.: On the Varshamov-Tenengol’ts construction on binary strings. Discret. Math. 317, 79–90 (2014).
Levenshtein V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Doklady 10(8), 707–710 (1966).
Levenshtein V.I.: On perfect codes in deletion and insertion metric. Discret. Math. Appl. 2(3), 241–258 (1992).
Marathe A., Condon A.E., Corn R.M.: On combinatorial DNA design. J. Comp. Biol. 8, 201–219 (2001).
Mercier H., Bhargava V.K., Tarokh V.: A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Commun. Surv. Tutor. 12(1), 87–96 (2010).
SageMath, the Sage Mathematics Software System (Version 8.6). The Sage Developers (2018) https://www.sagemath.org.
Schoeny C., Sala F., Dolecek L.: Novel combinatorial coding results for DNA sequencing and data storage. In: 2017 51st Asilomar Conference on Signals, Systems, and Computers. IEEE, pp. 511–515 (2017).
Sloane N.J.: On single-deletion-correcting codes. In: Proc. Codes and designs (Columbus, OH, 2000), pp. 273–291, Ohio State Univ. Math. Res. Inst. Publ., Berlin (2002).
Smith D., et al.: Interleaved constrained codes with markers correcting bursts of insertions or deletions. IEEE Commun. Lett. 21(4), 702–705 (2017).
Tulpan D., Smith D.H., Smith R.: Thermodynamic post-processing versus GC-content pre-processing for DNA codes satisfying the Hamming distance and reverse-complement constraints. IEEE/ACM Trans. Comput. Biol. Bioinform. 11(2), 441–452 (2014).
Varbanov Z., Todorov T., Hristova M.: A method for constructing DNA codes from additive self-dual codes over GF(4). In: Proc. CAIM conference, Romania, vol. 40 (2014).
Varshamov R.R., Tenengol’ts G.M.: Code correcting single asymmetric errors. Avtomat. Telemekh. 26(2), 288–292 (1965).
Acknowledgements
We thank anonymous referees for their helpful comments, which improved the clarity of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C. Carlet.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
W.-H. Choi: is supported by the National Research Foundation of Korea (NRF) Grant funded by the Korea government (NRF-2019R1I1A1A01057755), H.J. Kim: is supported by the National Research Foundation of Korea (NRF) Grant funded by the Korea government (NRF-2017R1D1A1B03028251) and (NRF-2020R1F1A1A01071645), and Y. Lee: is supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (Grant No. 2019R1A6A1A11051177) and also by the National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST)(NRF-2017R1A2B2004574).
Rights and permissions
About this article
Cite this article
Choi, WH., Kim, H.J. & Lee, Y. Construction of single-deletion-correcting DNA codes using CIS codes. Des. Codes Cryptogr. 88, 2581–2596 (2020). https://doi.org/10.1007/s10623-020-00802-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00802-2