DNA code construction refers to the application of coding theory to the design of nucleic acid systems for the field of DNA–based computation.
Introduction
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. For the purpose of this entry, we shall focus on only oligonucleotides. DNA computing involves allowing synthetic oligonucleotide strands to hybridize in such a way as to perform computation. DNA computing requires that the self-assembly of the oligonucleotide strands happen in such a way that hybridization should occur in a manner compatible with the goals of computation.
The field of DNA computing was established in Leonard M. Adelman's seminal paper. His work is significant for a number of reasons:
It shows how one could use the highly parallel nature of computation performed by DNA to solve problems that are difficult or almost impossible to solve using the traditional methods. It's an example of computation at a molecular level, on the lines of nanocomputing, and this potentially is a major advantage as far as the information density on storage media is considered, which can never be reached by the semiconductor industry. It demonstrates unique aspects of DNA as a data structure.
This capability for massively parallel computation in DNA computing can be exploited in solving many computational problems on an enormously large scale such as cell-based computational systems for cancer diagnostics and treatment, and ultra-high density storage media.
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. This is also known as self-hybridization). The Nussinov-Jacobson algorithm is used to predict secondary structures and also to identify certain design criteria that reduce the possibility of secondary structure formation in a codeword. 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.
Definitions
A DNA code is simply a set of sequences over the alphabet .
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. This pairing can be described as follows – .
Such pairing is chemically very stable and strong. However, pairing of mismatching bases does occur at times due to biological mutations.
Most of the focus on DNA coding has been on constructing large sets of DNA codewords with prescribed minimum distance properties. For this purpose let us lay down the required groundwork to proceed further.
Let be a word of length over the alphabet . For , we will use the notation to denote the subsequence . Furthermore, the sequence obtained by reversing will be denoted as . The Watson-Crick complement, or the reverse-complement of q, is defined to be , where denotes the Watson-Crick complement base pair of .
For any pair of length- words and over , the Hamming distance is the number of positions at which . Further, define reverse-Hamming distance as . Similarly, reverse-complement Hamming distance is . (where 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 GC-content, , of a DNA sequence is defined to be the number of indices such that . A DNA code in which all codewords have the same GC-content, , is called a constant GC-content code.
A generalized Hadamard matrix is an square matrix with entries taken from the set of th roots of unity, , that satisfies = . Here denotes the identity matrix of order , while * stands for complex-conjugation. We will only concern ourselves with the case for some prime . A necessary condition for the existence of generalized Hadamard matrices is that . The exponent matrix, , of is the matrix with the entries in , is obtained by replacing each entry in by the exponent .
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.
Here, the elements of lie in the Galois field .
By definition, a generalized Hadamard matrix in its standard form has only 1s in its first row and column. The square matrix formed by the remaining entries of is called the core of , and the corresponding submatrix of the exponent matrix is called the core of construction. 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.
Also, the rows of such an exponent matrix satisfy the following two properties: (i) in each of the nonzero rows of the exponent matrix, each element of appears a constant number, , of times; and (ii) the Hamming distance between any two rows is .
Property U Let be the cyclic group generated by , where is a complex primitive th root of unity, and is a fixed prime. Further, let , denote arbitrary vectors over which are of length , where is a positive integer. Define the collection of differences between exponents , where is the multiplicity of element of which appears in .
Vector is said to satisfy Property U if and only if each element of appears in exactly times ()
The following lemma is of fundamental importance in constructing generalized Hadamard codes.
Lemma. Orthogonality of vectors over – For fixed primes , arbitrary vectors of length , whose elements are from , are orthogonal if the vector satisfies Property U, where is the collection of differences between the Hadamard exponents associated with .
M sequences
Let be an arbitrary vector of length whose elements are in the finite field , where is a prime. Let the elements of a vector constitute the first period of an infinite sequence which is periodic of period . If is the smallest period for conceiving any subsequence, the sequence is called an M-sequence, or a maximal sequence of least period obtained by cyclically permuting elements. If whenever the elements of are permuted arbitrarily to yield , the sequence is an M-sequence, then the sequence is called M-invariant. The theorems that follow present conditions that ensure M-invariance. 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.
The goal here is to find cyclic matrix whose elements are in Galois field and whose dimension is . The rows of will be the nonzero codewords of a linear cyclic code , if and only if there is polynomial with coefficients in , which is a proper divisor of and which generates . In order to have nonzero codewords, must be of degree . Further, in order to generate a cyclic Hadamard core, the vector (of coefficients of) when operated upon with the cyclic shift operation must be of period , and the vector difference of two arbitrary rows of (augmented with zero) must satisfy the uniformity condition of Butson, previously referred to as Property U. One necessary condition for -periodicity is that , where is monic irreducible over. The approach here is to replace the last requirement with the condition that the coefficients of the vector are uniformly distributed over , i.e. each residue appears the same number of times (Property U). A proof that this heuristic approach always produces a cyclic core is given below.
Examples of code construction
Code construction using complex Hadamard matrices
Construction algorithm Consider a monic irreducible polynomial over of degree having a suitable companion of degree such that , where the vector satisfies Property U. This requires only a simple computer algorithm for long division over . Since , the ideal generated by is a cyclic code . Moreover, Property U guarantees the nonzero codewords form a cyclic matrix, each row of period under cyclic permutation, which serves as a cyclic core for the Hadamard matrix . As an example, a cyclic core for results from the companions and . The coefficients of indicate that is the relative difference set, .
Theorem Let be a prime and , with a monic polynomial of degree whose extended vector of coefficients are elements of . Suppose the following conditions hold:
vector satisfies the property U, and , where is a monic irreducible polynomial of degree .
Then there exists a p-ary linear cyclic code of blocksize , such that the augmented code is the exponent matrix for the Hadamard matrix , with , where the core of is a cyclic matrix.
Proof:
First note that is monic and divides with degree . Now, we need to show that the matrix whose rows are nonzero codewords constitutes a cyclic core for some complex Hadamard matrix .
Given that satisfies property U, all of the nonzero residues of lie in C. By cyclically permuting elements of , we get the desired exponent matrix where we can get every codeword in by permuting the first codeword. (This is because the sequence obtained by cyclically permuting is M-invariant.)
We also see that augmentation of each codeword of by adding a leading zero element produces a vector which satisfies Property U. Also, since the code is linear, the vector difference of two arbitrary codewords is also a codeword and thus satisfy Property U. Therefore, the row vectors of the augmented code form a Hadamard exponent. Thus, is the standard form of some complex Hadamard matrix .
Thus from the above property, we see that the core of is a circulant matrix consisting of all the cyclic shifts of its first row. Such a core is called a cyclic core where in each element of appears in each row of exactly times, and the Hamming distance between any two rows is exactly . The rows of the core form a constant-composition code - one consisting of cyclic shifts of some length over the set . Hamming distance between any two codewords in is .
The following can be inferred from the theorem as explained above. (For more detailed reading, the reader is referred to the paper by Heng and Cooke.) Let for prime and . Let be a monic polynomial over , of degree N − k such that over , for some monic irreducible polynomial . Suppose that the vector , with for (N − k) < i < N, has the property that it contains each element of the same number of times. Then, the cyclic shifts of the vector form the core of the exponent matrix of some Hadamard matrix .