Constructing DNA Codes with Larger Distance from Quaternary Words

Benediktus Panji Pradipta; Nikken Prima Puspita

doi:10.37905/jjom.v7i2.33132

Constructing DNA Codes with Larger Distance from Quaternary Words

Benediktus Panji Pradipta, Nikken Prima Puspita

Abstract

In this work, we propose a novel method to construct DNA codes from quaternary words. The method uses permutation groups that act in the set {1, 2, …, 4n}, representing the coordinate and coordinate value of quaternary words. The DNA code is obtained by finding a clique of the construction graph and mapping it using the bijective map 0 → A, 1 → C, 2 → T, 3 → G. We present a new approach to construct DNA codes with larger Hamming distance and reverse-complement distance compared to previously obtained DNA codes. This is achieved by using a modified construction graph tailored to the desired distance parameter. As a result, we can refine a DNA code to have improved Hamming distance and reverse-complement distance while maintaining the fixed GC-content constraint. This method simplifies the search for DNA codes with large distance parameters.

Keywords

DNA codes; clique; permutation group; minimum distance

Full Text:

PDF

References

T. Head, “Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors,” Bull. Math. Biol., vol. 49, no. 6, pp. 737–759, 1987, doi: 10.1016/S0092-8240(87)90018-8.

L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science, vol. 266, no. 5187, pp. 1021–1024, Nov. 1994, doi: 10.1126/science.7973651.

D. Limbachiya and M. K. Gupta, “On Designing DNA Codes and their Applications,” Dhirubhai Ambani Institute of Information and Communication Technology, 2019.

P. Gaborit and O. D. King, “Linear constructions for DNA codes,” Theor. Comput. Sci., vol. 334, no. 1–3, pp. 99–113, Apr. 2005, doi: 10.1016/j.tcs.2004.11.004.

H. J. Kim, W. H. Choi, and Y. Lee, “Designing DNA codes from reversible self-dual codes over GF(4),” Discrete Math., vol. 344, no. 1, Jan. 2021, doi: 10.1016/j.disc.2020.112159.

S. Houghten and S. Banik, “Effective decoders for DNA codes,” BioSystems, vol. 211, Jan. 2022, doi: 10.1016/j.biosystems.2021.104583.

A. Nicolaidis and F. Psomopoulos, “DNA coding and Gödel numbering,” Physica A: Stat. Mech. Appl., vol. 594, May 2022, doi: 10.1016/j.physa.2022.127053.

S. V. Petoukhov, “Genetic code, the problem of coding biological cycles, and cyclic Gray codes,” BioSystems, vol. 246, Dec. 2024, doi: 10.1016/j.biosystems.2024.105349.

B. Feng, S. S. Bai, B. Y. Chen, and X. N. Zhou, “The constructions of DNA codes from linear self-dual codes over ℤ₄,” 2015, doi: 10.2991/cisia-15.2015.135.

J. Xu, W. Liu, K. Zhang, and E. Zhu, “DNA coding theory and algorithms,” Artif. Intell. Rev., vol. 58, no. 6, Jun. 2025, doi: 10.1007/s10462-025-11132-x.

A. Laaksonen and P. R. J. Östergård, “New lower bounds on q-ary error-correcting codes,” Cryptogr. Commun., vol. 11, no. 5, pp. 881–889, Sep. 2019, doi: 10.1007/s12095-018-0302-9.

A. Laaksonen and P. R. J. Östergård, “Constructing error-correcting binary codes using transitive permutation groups,” Discrete Appl. Math., vol. 233, pp. 65–70, Dec. 2017, doi: 10.1016/j.dam.2017.08.022.

A. Marathe, A. E. Condon, and R. M. Corn, “On combinatorial DNA word design,” J. Comput. Biol., vol. 8, no. 3, pp. 201–219, Jun. 2001, doi: 10.1089/10665270152530818.

D. Limbachiya, B. Rao, and M. K. Gupta, “The art of DNA strings: Sixteen years of DNA coding theory,” Jul. 2016, [Online]. Available: http://arxiv.org/abs/1607.00266.

S. Niskanen and P. R. J. Östergård, Cliquer User’s Guide, Version 10, Espoo, Finland: Communications Laboratory, Tech. Rep. T48, Helsinki Univ. of Technology, 2003.

DOI: https://doi.org/10.37905/jjom.v7i2.33132