DNA sequences are known to appear in the form of double helices in living cells, in which one DNA strand is hybridized to its complementary strand through a series of hydrogen bonds.
The field of DNA computing was established in Leonard M. Adelman's seminal paper.
[2] This selection of codewords (sequences of DNA oligonucleotides) is a major hurdle in itself due to the phenomenon of secondary structure formation (in which DNA strands tend to fold onto themselves during hybridization and hence rendering themselves useless in further computations.
In essence this algorithm shows how the presence of a cyclic structure in a DNA code reduces the complexity of the problem of testing the codewords for secondary structures.
Novel constructions of such codes include using cyclic reversible extended generalized Hadamard matrices, and a binary approach.
Before diving into these constructions, we shall revisit certain fundamental genetic terminology.
The motivation for the theorems presented in this article, is that they concur with the Nussinov - Jacobson algorithm, in that the existence of cyclic structure helps in reducing complexity and thus prevents secondary structure formation.
i.e. these algorithms satisfy some or all the design requirements for DNA oligonucleotides at the time of hybridization (which is the core of the DNA computing process) and hence do not suffer from the problems of self - hybridization.
Each purine base is the Watson-Crick complement of a unique pyrimidine base (and vice versa) – adenine and thymine form a complementary pair, as do guanine and cytosine.
However, pairing of mismatching bases does occur at times due to biological mutations.
stands for reverse complement) Another important code design consideration linked to the process of oligonucleotide hybridization pertains to the GC content of sequences in a DNA code.
The elements of the Hadamard exponent matrix lie in the Galois field
, and its row vectors constitute the codewords of what shall be called a generalized Hadamard code.
Thus, by omission of the all-zero first column cyclic generalized Hadamard codes are possible, whose codewords are the row vectors of the punctured matrix.
) The following lemma is of fundamental importance in constructing generalized Hadamard codes.
In conjunction with a certain uniformity property of polynomial coefficients, these conditions yield a simple method by which complex Hadamard matrices with cyclic core can be constructed.
Further, in order to generate a cyclic Hadamard core, the vector (of coefficients of)
(augmented with zero) must satisfy the uniformity condition of Butson,[5] previously referred to as Property U.
Moreover, Property U guarantees the nonzero codewords form a cyclic matrix, each row of period
Suppose the following conditions hold: Then there exists a p-ary linear cyclic code
whose rows are nonzero codewords constitutes a cyclic core for some complex Hadamard matrix
by adding a leading zero element produces a vector which satisfies Property U.
(For more detailed reading, the reader is referred to the paper by Heng and Cooke.
guaranteed by the theorem proved above and the resulting property, and using the mapping that takes
Each of the following vectors generates a cyclic core of a Hadamard matrix
The actual choice of mapping plays a major role in secondary structure formations in the codewords.
However the actual choice of mapping has a strong influence on the secondary structure of the codewords.
As we can see, the first bit of a binary image clearly determines which complementary pair it belongs to.
because of the sheer flexibility and speed as well as cost factors that favor silicon chip based devices used for the computers today.
[2] However, such a method could be used in situations where the only available method is this and requires the accuracy associated with the DNA hybridization mechanism; applications which require operations to be performed with a high degree of reliability.