Construction of cyclic codes over for DNA computing☆
Introduction
DNA computing started in 1994 when Leonard Adleman solved a hard (NP-complete) computational problem such as the Hamiltonian Path problem by manipulations of DNA molecules in a test tube [1]. Because of the huge numbers of DNA molecules in a typical test tube, any method of computation based on DNA would seem to have potential for a massive parallelism, capacity, and power. This potential, however, is limited by the constraints imposed by the chemical structure of DNA.
A single DNA strand is a sequence of four possible nucleotides: adenine (A), guanine (G), cytosine (C) and thymine (T). The ends of a single DNA strand are chemically polar with the so-called end and the end. Since there are possible single DNA strands of length , and since DNA strands can be quickly and cheaply synthesized, DNA codewords can be used to store information at the molecular level, thereby providing a basis for bimolecular computation. It is known that 1 g of DNA contains DNA bases. Since there are four DNA bases, each DNA basis can encode two bits which implies that 1 g of DNA can store about bits. In contrast, conventional storage technologies can store at most bits.
Applications of DNA require success in achieving specific hybridization between a DNA codeword and its Watson–Crick complement, while minimizing false-positive and false-negative signals. Each single string can be paired up with a complementary string to form a double helix. The Watson–Crick complement of a DNA strand is the strand obtained by replacing each A by and vice versa, each C by G and vice versa, and switching the and ends. For example, the Watson–Crick complement of -- is --. Specific hybridization is the process whereby a strand and its Watson–Crick complement bond to form a double helix. A false-positive results when a non-specific hybridization occurs, such as the one between a DNA strand and the Watson–Crick complement of a different DNA strand. Non-specific hybridization may also occur between a DNA strand and the reverse of a distinct strand. A false negative occurs when hybridization between a DNA strand and its Watson–Crick complement does not occur.
Several papers have proposed different techniques to construct a set of DNA codewords that are unlikely to form undesirable bonds with each other by hybridization [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]. For example, in [6], [7], [8], four different constraints on DNA codes are considered, which are: the Hamming constraint for distance , the reverse-complement constraint, the reverse constraint and the fixed -content (all codewords in this case have the same number of and ) constraint. The purpose of the first three constraints is to make non-desirable hybridizations difficult to occur. The fixed -content constraint is used to make sure that similar melting temperatures are obtained [8]. In [9], the authors use stochastic search algorithms to design codewords that are suitable for DNA computing. In [10], [11], the authors develop genetic and evolutionary algorithms which select sets of DNA sequences that are less likely to form undesirable bonds. Also, in [12], the authors propose to use cyclic codes over to construct DNA codes. However, they restrict their work to only linear reversible cyclic codes over .
In this paper, we use the theory of cyclic codes to construct codes that are suitable for DNA computing. In particular, we construct both linear and additive cyclic codes over that are suitable for this application. Our interest in additive codes over has been motivated by the correspondence between these codes and quantum codes, as described in [13]. The main advantage of additive codes over linear codes is that, for the same code length, there are more additive codes than linear codes. Therefore, it is more likely to find an additive code that has more codewords than a linear code with the same minimum Hamming distance (for both codes).
We first develop the theory for constructing linear and additive codes of odd length over that satisfy the first three constraints mentioned above. Once such codes are constructed, the -content constraint can be easily incorporated by removing the codewords that violate this constraint. We use this theory to construct all linear and additive codes of length , , , and . We show that some of these codes have more codewords than the best previously known codes with the same minimum Hamming distance. The consequence of having more codewords is an increase in the number of valid DNA sequences, and hence more storage.
The rest of the paper is organized as follows. In Section 1, we give some background and recall some basic results for DNA codes and cyclic codes over . In Section 2, we develop the theory for constructing linear and additive reversible complement cyclic codes over . In Section 3, we list the best reversible complement cyclic codes of lengths , , , and . Finally, Section 4 concludes the paper.
Section snippets
Background
DNA occurs in sequences, represented by sequences of letters from the alphabet . We define a DNA code of length n to be a set of codewords where . These codewords must satisfy the four constraints mentioned above. In this paper, we shall associate codes over with codes over with , and . The letters , , , and T map to , , , and , respectively. The Watson–Crick complement is given by , , , and . For each
Cyclic reversible complement codes over
Lemma 5 Let where , , and are nontrivial polynomials that divide in . Then if and are self-reciprocal then is self-reciprocal, if either or (but not both) is not self-reciprocal then is not self-reciprocal, if and are not self-reciprocal then might be self-reciprocal.
Proof
Let where , , and are nontrivial polynomials that divide in
Results
In this section, we use the theory developed above to study linear and additive reversible complement cyclic codes over of lengths , , , and . For the linear case there are only few codes, which are:
- •
Length : There is one code given by
- •
Length : There are three codes given by and
- •
Length 11: There is one code given by
- •
Length 13: There is one code given by
Concluding remarks
In this paper, we have developed the theory for constructing linear and additive cyclic codes of odd length over that are suitable for DNA computing. We have studied all such codes of lengths , , , and We have shown that some of these codes have more codewords than the best previously known codes with the same Hamming distance.
References (17)
Reversible codes
Inf. Control
(1964)Molecular computation of solutions to combinatorial problems
Science
(1994)- R. Deaton, R. Murphy, M. Garzon, D.R. Franceschetti, S.E. Stevens, Good encoding for DNA-based solutions to...
- M. Garzon, P. Neathery, R. Deaton, M. Garzon, R.C. Murphy, D.R. Franceschetti, S.E. Stevens Jr., A new metric for DNA...
- M. Garzon, R. Deaton, L.F. Nino, S.E. Stevens Jr., M. Wittner, Genome encoding for DNA computing, Proceedings of the...
- L. Kari, R. Kitto, G. Thierrin, Codes, Involutions, and DNA Encoding, Lecture Notes in Computer Science, vol. 2300,...
Bounds for DNA codes with constant GC-content
J. Combin.
(2003)- et al.
On combinatorial DNA word design
J. Comput. Biol.
(2001)
Cited by (65)
DNA codes over finite local Frobenius non-chain rings of length 4
2021, Discrete MathematicsFuture DNA computing device and accompanied tool stack: Towards high-throughput computation
2021, Future Generation Computer SystemsCitation Excerpt :The DNA computing technology relies on the DNA reaction mechanism such as DSD [11], DNA walker [10], programmable self-assembly [20], and others [21,22]. Those mechanism reveals the underlying components of digital logic circuits in DNA computing and the hierarchy they scale up to form the integrated circuits [23]. In particular, the lasted developed techniques are mostly based on the DSD mechanism for its robustness in the stochastic nature of molecular reactions [24].
Designing DNA codes from reversible self-dual codes over GF(4)
2021, Discrete MathematicsReversible complement cyclic codes over Galois rings with application to DNA codes
2020, Discrete Applied MathematicsCitation Excerpt :Prior to our work, complement of an element in a ring has been defined in different ways by various authors. For reference see [1,3–5,7,8,10,11,16,19–22,24,25,30]. The following result is due to Kaur et al. [13].
REVERSIBLE G-CODES OVER THE RING F<inf>j,k</inf> WITH APPLICATIONS TO DNA CODES
2023, Advances in Mathematics of Communications
- ☆
This work was supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC) Grant N00858, and was performed while the first author was on a short-term appointment in the Electrical and Computer Engineering Department, Concordia University, Montreal, Que., Canada.