Coding theory approaches to nucleic acid design


Coding theory approaches to nucleic acid design

DNA code construction refers to the application of coding theory to the design of nucleic acid systems for the field of DNA–based computation.

Contents

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.[1] 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.[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. This is also known as self-hybridization). The Nussinov-Jacobson[3] 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 Goppa codes, 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 \mathcal{Q} = \{ \mathit{A}, \mathit{T}, \mathit{C}, \mathit{G} \}.

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 –  \bar{A} = T, \bar{T} = A, \bar{C} = G, \bar{G} = C .

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 q = q1q2....qn be a word of length n over the alphabet \mathcal{Q}. For 1 \leqslant i \leqslant j \leqslant n, we will use the notation q[i,j] to denote the subsequence qiqi + 1...qj. Furthermore, the sequence obtained by reversing q will be denoted as qR. The Watson-Crick complement, or the reverse-complement of q, is defined to be \mathit{q}^{RC} = \mathit{\bar{q}_n}\mathit{\bar{q}_{n-1}} ... \mathit{\bar{q}_1}, where \mathit{\bar{q}_i} denotes the Watson-Crick complement base pair of qi.

For any pair of length-n words p and q over \mathcal{Q}, the Hamming distance dH(p,q) is the number of positions i at which \mathit{p}_i \neq \mathit{q}_i. Further, define reverse-Hamming distance as \mathit{d_H}^R(\mathit{p},\mathit{q}) = \mathit{d}_H(\mathit{p},\mathit{q}^R). Similarly, reverse-complement Hamming distance is \mathit{d}_H^{RC}(\mathit{p},\mathit{q}) = \mathit{d}_H(\mathit{p},\mathit{q}^{RC}). (where RC 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, wGC(q), of a DNA sequence q = q1q2....qn is defined to be the number of indices i such that \mathit{q}_i \in \{G, C\}. A DNA code in which all codewords have the same GC-content, w, is called a constant GC-content code.

A generalized Hadamard matrix \mathit{H} \equiv \mathit{H}(n, \mathbb{C}_m) is an n \times n square matrix with entries taken from the set of mth roots of unity, \mathbb{C}_m= {e − 2πil / m, l = 0, ..., m − 1}, that satisfies HH * = nI. Here I denotes the identity matrix of order n, while * stands for complex-congugation. We will only concern ourselves with the case m = p for some prime p. A necessary condition for the existence of generalized Hadamard matrices \mathit{H}( \mathit{n}, \mathbb{C}_p) is that p | n. The exponent matrix, E (\mathit{n},\mathbb{Z}_p), of \mathit{H}(\mathit{n},\mathbb{C}_p) is the \mathit{n}\times\mathit{n} matrix with the entries in Zp = {0,1,2,...,p − 1}, is obtained by replacing each entry (e − 2πil) in \mathit{H}(\mathit{n},\mathbb{C}_p) by the exponent l.

The elements of the Hadamard exponent matrix lie in the Galois field GF(p), and its row vectors constitute the codewords of what shall be called a generalized Hadamard code.

Here, the elements of E lie in the Galois field GF(p).

By definition, a generalized Hadamard matrix H in its standard form has only 1s in its first row and column. The (\mathit{n} - 1) \times (\mathit{n} - 1) square matrix formed by the remaining entries of H is called the core of H, and the corresponding submatrix of the exponent matrix E 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 \mathbb{Z}_p appears a constant number, n / p, of times; and (ii) the Hamming distance between any two rows is n(p − 1) / p.[4]

Property U

Let Cp = 1,x,x2,...,xpI be the cyclic group generated by x, where x = exp(2πj / p) is a complex primitive pth root of unity, and p > 2 is a fixed prime. Further, let \mathit{A} = (x^{a_i}), \mathit{B} = (x^{b_i}) denote arbitrary vectors over Cp which are of length N = pt, where t is a positive integer. Define the collection of differences between exponents \mathit{Q} = {\mathit{a_i} - \mathit{b_i} \mod \mathit{p} : i = 1, 2,..., N}, where nq is the multiplicity of element q of GF(p) which appears in Q.[4]

Vector Q is said to satisfy Property U iff each element q of GF(p) appears in Q exactly t times (nq = t,q = 0,1,...,p − 1)

The following lemma is of fundamental importance in constructing generalized Hadamard codes.

Lemma. Orthogonality of vectors over Cp - For fixed primes p, arbitrary vectors A,B of length N = pt, whose elements are from Cp, are orthogonal if the vector Q satisfies Property U, where Q is the collection of modp differences between the Hadamard exponents associated with A,B.

M sequences

Let V be an arbitrary vector of length N whose elements are in the finite field GF(p), where p is a prime. Let the elements of vector V constitute the first period of an infinite sequence a(V) which is periodic of period N. If N is the smallest period for conceiving a subsequence, the sequence is called an M-sequence, or a sequence of maximal least period obtained by cycling N elements. If, when the elements of the ordered set V are permuted arbitrarily to yield V * , the sequence a(V * ) is an M-sequence, the sequence a(V) is called M-invariant. The theorems that follow present conditions that ensure invariance in an M sequence. In conjunction with a certain uniformity property of polynomial coeffecients, these conditions yield a simple method by which complex Hadamard matrices with cyclic core can be constructed.

The goal as outlined at the head of this article is to find cyclic matrix E = Ec whose elements are in Galois field GF(p) and whose dimension is N = pn1. The rows of E will be the nonzero codewords of a linear cyclic code K, if and only if there is polynomial g(x) with coefficients in GF(p), which is a proper divisor of xN1 and which generates K. In order to haveN nonzero codewords, g(x) must be of degree Nn. Further, in order to generate a cyclic Hadamard core, the vector (of coefficients of) g(x) when operated upon with the cyclic shift operation must be of period N, and the vector difference of two arbitrary rows of E (augmented with zero) must satisfy the uniformity condition of Butson,[5] previously referred to as Property U. One necessary condition for N-peridoicity is that xN1 = g(x)h(x), where h(x) is monic irreducible over.[6] The approach here is to replace the last requirement with the condition that the coefficients of the vector [0,g(x)] be uniformly distributed over GF(p), each residue 0,1,...,p − 1 appears the same number of times (Property U). This heuristic approach has succeeded for all cases tried, and a proof that it always produces a cyclic core is given below.

Examples of code construction

1. Code construction using complex Hadamard matrices

Construction algorithm

Consider all monic irreducible polynomials h(x) over GF(p) which are of degree n , and which permit a suitable companion g(x) of degree Nn such that g(x)h(x) = xN − 1, where also vector [0,g(x)] satisfies Property U. This requires only a simple computer algorithm for long division over GF(p). Since h(x) | xN − 1, the ideal generated by g(x) , \mod xN − 1, will be a cyclic code K. Moreover, Property U guarantees the nonzero codewords form a cyclic matrix, each row being of period N under cyclic permutation, which serves as a cyclic core for Hadamard matrix H(p,pn). As an example, a cyclic core for H(3,9) results from the companions h(x) = x2 + x + 2 and g(x) = x6 + 2x5 + 2x4 + 2x2 + x + 1. The coefficients of g indicate that 0,1,6 is the relative difference set, \mod 8.

Theorem

Let p be a prime and N + 1 = pn, with g(x) a monic polynomial of degree Nn whose extended vector of coefficients C = [c0,c1,...,cN − 1] are elements of GF(p). The conditions are as follows:

(1) vector C = [c0,c1,...,cN − 1] satisfies the property U explained above,

(2) g(x)h(x) = xN1, where h(x) is a monic irreducible polynomial of degree n, guarantee the existence of a p-ary, linear cyclic code \mathit{\bar{K}}: of blocksize N, such that the augmented code \mathit{K} = [0, \mathit{\bar{K}}] is the Hadamard exponent, for Hadamard matrix H(p,pn) = xK, with x = e2πi / p, where the core of H is cyclic matrix.

Proof:

First, we note that since g(x) is monic, it divides xN1, and has degree = Nn. Now, we need to show that the matrix Ec whose rows are the nonzero codewords, constitutes a cyclic core for some complex Hadamard matrix H.

Given: we know that C satisfies property U. Hence, all of the nonzero residues of GF(p) lie in C. By cycling through C, we get the desired exponent matrix Ec where we can get every codeword in Ec by cycling the first codeword. (This is because the sequence obtained by cycling through C is an M-invariant sequence.)

We also see that augmentation of each codeword of Ec by adding a leading zero element produces a vector which satisfies Property U. Also, since the code is linear, the \mod p vector difference of two arbitrary codewords is also a codeword and thus satisfy Property U. Therefore, the row vectors of the augmented code K form a Hadamard exponent. Thus, xK is the standard form of some complex Hadamard matrix H.

Thus from the above property, we see that the core of E is a circulant matrix consisting of all the N = pk − 1 cyclic shifts of its first row. Such a core is called a cyclic core where in each element of \mathbb{Z}_p appears in each row of E exactly (N + 1) / p = pk − 1 times, and the Hamming distance between any two rows is exactly (N + 1)(p − 1) / p = (p1)pk − 1. The N rows of the core E form a constant-composition code - one consisting of N cyclic shifts of some length N over the set \mathbb{Z}_p. Hamming distance between any two codewords in \mathbb{Z}_p is (p1)pk − 1.

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.[4]) Let N = pk − 1 for p prime and \mathit{k} \in \mathbb{Z}^+. Let g(x) = c0 + c1x + c2x2 + ... + cNkxNk be a monic polynomial over \mathbb{Z}_p, of degree N - k such that g(x)h(x) = xN − 1 over \mathbb{Z}_p, for some monic irreducible polynomial \mathit{h}(\mathit{x}) \in \mathbb{Z}_p[\mathit{x}]. Suppose that the vector (c0,c1,....,cNk,cNk + 1,...,cN − 1), with ci = 0 for (N - k) < i < N, has the property that it contains each element of \mathbb{Z}_p the same number of times. Then, the N cyclic shifts of the vector g = (c0,c1,...,cN − 1) form the core of the exponent matrix of some Hadamard matrix .

DNA codes with constant GC-content can obviously be constructed from constant-composition codes (A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword) over \mathbb{Z}_p by mapping the symbols of \mathbb{Z}_p to the symbols of the DNA alphabet, \mathcal{Q} = \{ \mathit{A}, \mathit{T}, \mathit{C}, \mathit{G} \}. For example, using cyclic constant composition code of length 3k − 1 over \mathbb{Z}_3 guaranteed by the theorem proved above and the resulting property, and using the mapping that takes 0 to A, 1 to T and 2 to G, we obtain a DNA code \mathcal{D} with 3k − 1 and a GC-content of 3k − 1. Clearly dH = 2.3k − 1 and in fact since \mathit{\bar{G}}=\mathit{C} and no codeword in \mathcal{D} contains no symbol C, we also have \mathit{d}_H^{RC}(\mathcal{D}) \geq 3^{k - 1}. This is summarized in the following corollary.[4]

Corollary

For any \mathit{k} \in \mathbb{Z}^+, there exists DNA codes \mathbb{D} with 3k − 1 codewords of length 3k − 1, constant GC-content 3k − 1, \mathit{d}_H^{RC}(\mathbb{D}) \geqslant \mathit{3}^{k-1} and in which every codeword is a cyclic shift of a fixed generator codeword g.

Each of the following vectors generates a cyclic core of a Hadamard matrix H(p,pn) (where N + 1 = pn, and n = 3 in this example)[4] :

g(1) = (22201221202001110211210200);

g(2) = (20212210222001012112011100).

Where, g(x) = a0 + a1x + .... + anxn.

Thus, we see how DNA codes can be obtained from such generators by mapping 0,1,2 onto A,T,G. The actual choice of mapping plays a major role in secondary structure formations in the codewords.

We see that all such mappings yield codes with essentially the same parameters. However the actual choice of mapping has a strong influence on the secondary structure of the codewords. For example, the codeword illustrated was obtained from g(1) via the mapping 0 − A;1 − T;2 − G, while the codeword g(2) was obtained from the same generator g(1) via the mapping 0 − G;1 − T;2 − A.

2. Code construction via a Binary Mapping

Perhaps a simpler approach to building/designing DNA codewords is by having a binary mapping by looking at the design problem as that of constructing the codewords as binary codes. i.e. map the DNA codeword alphabet \mathcal{Q} onto the set of 2-bit length binary words as shown: A -> 00, T -> 01, C -> 10, G ->11.

As we can see, the first bit of a binary image clearly determines which complementary pair it belongs to.

Let q be a DNA sequence. The sequence b(q) obtained by applying the mapping given above to q, is called the binary image of q.

Now, let b(q) = b0b1b2...b2n − 1.

Now, let the subsequence e(q) = b0b2...b2n − 2 be called the even subsequence of b(q), and o(q) = b1b3b5...b2n − 1 be called the odd subsequence of b(q).

Thus, for example, for q = ACGTCC, then, b(q) = 001011011010.

e(q) will then be = 011011 and o(q) = 001100.

Let us define an even component as \mathcal{E}(\mathcal{C}) = \{ e(x) : x \in \mathcal{C}\}, and an odd component as \mathcal{O} (\mathcal{C}) = \{ o(x) : x \in \mathcal{C}\}.

From this choice of binary mapping, the GC-content of DNA sequence q = Hamming weight of e(q).

Hence, a DNA code \mathcal{C} is a constant GC-content codeword if and only if its even component \mathcal{E}(\mathcal{C}) is a constant-weight code.

Let \mathcal{B} be a binary code consisting of M codewords of length n and minimum distance dmin, such that \mathit{c} \in \mathcal{B} implies that \mathit{\bar{c}} \in \mathcal{B}.

For w > 0, consider the constant-weight subcode \mathcal{B_{\mathit{w}}} = \{u \in \mathcal{B} : \mathit{w_H}(u) = \mathit{w} \}, where wH(.) denotes Hamming weight. Choose w > 0 such that \mathit{n} \geq \mathit{2w} + \lceil \mathit{d_{min}}/2 \rceil, and consider a DNA code, \mathcal{C}_w, with the following choice for its even and odd components:

\mathcal{E} = \{a \bar{b} : a, b \in \mathcal{B}_w \}, \mathcal{O} = \{ab^{RC} : a, b \in \mathcal{B}, a <lexb}.

Where < lex denotes lexicographic ordering. The a < lexb in the definition of \mathcal{O} ensures that if ab^{RC} \in \mathcal{O}, then ba^{RC} \notin \mathcal{O}, so that distinct codewords in \mathcal{O} cannot be reverse-complements of each other.

The code \mathcal{E}_w has {\left\vert \mathcal{B}_w \right\vert} ^2 codewords of length 2n and constant weight n.

Furthermore, \mathit{d_H}(\mathcal{E}_w \geq \mathit{d_{min}}) and \mathit{d_H}^{R}(\mathcal{E}_w \geq \mathit{d_{min}}) ( this is because \mathcal{B}_w is a subset of the codewords in \mathcal{B}).

Also, \mathit{d_H}(a \bar{b}, d^{RC}c^R) = \mathit{d_H}(a,d^{RC}) + \mathit{d_H}(\bar{b}, c^R) = \mathit{d_H}(a, d^{RC}) + \mathit{d_H}(c, b^{RC}).

Note that b and d both have weight w. This implies that bRC and dRC have weight nw.

And due to the weight constraint on w, we must have for all a, b, c, d \in \mathcal{B}_w, \mathit{d_H}(a \bar{b}, d^{RC}c^R) \geq 2 \lceil \mathit{d_{min}} /2 \rceil \geq \mathit{d_{min}}.

Thus, the code \mathcal{O} has M(M − 1) / 2 codewords of length 2n.

From this, we see that \mathit{d_H}(\mathcal(O)) \geq \mathit{d_{min}} (because of the fact that the component codewords of \mathcal(O) are taken from \mathcal{B}).

Similarly, \mathit{d_H^{RC}}(\mathcal(O)) \geq \mathit{d_{min}}.

Therefore, the DNA code

 \mathcal{C} = \bigcup_{\mathit{w}=d_{min}}^{\mathit{w_{max}}} \mathcal{C}_w

with \mathit{w_{max}} = (\mathit{n} - \lceil d_{min}/2 \rceil )/2, has \frac {1} {2} M(M - 1) \sum_{w=d_{min}}^{w_{max}} \left\vert \mathit{A_w}^2 \right\vert codewords of length 2n, and satisfies \mathit{d_H}(\mathcal{B}) \geq \mathit{d_{min}} and \mathit{d_H}^{RC}(\mathcal{B}) \geq \mathit{d_{min}} .

From the examples listed above, one can wonder what could be the future potential of DNA-based computers?

Despite its enormous potential, this method is highly unlikely to be implemented in home computers or even computers at offices, etc. 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.

Currently, there are several software packages, such as the Vienna package,[7] which can predict secondary structure formations in single stranded DNAs (i.e. oligonucleotides) or RNA sequences.

See also

References

  1. ^ Molecular computation of solutions to combinatorial problem. http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf. 
  2. ^ a b M. Mansuripur, P.K. Khulbe, S.M. Kuebler, J.W. Perry, M.S. Giridhar and N.Peyghambarian Information storage and retrieval using macromolecules as storage media. http://www.opticsinfobase.org/view_article.cfm?gotourl=http%3A%2F%2Fwww.opticsinfobase.org%2FDirectPDFAccess%2F17ADF6D8-BDB9-137E-C485E432FB3BB804_113204.pdf%3Fda%3D1%26id%3D113204%26seq%3D0&org=State%20University%20of%20New%20York%20at%20Buffalo%20Lockwood%20Library. , University of Arizona Technical Report, 2003.
  3. ^ Olgica Milenkovic and Navin Kashyap, On the Design of codes for DNA computing. http://www.springerlink.com/content/d81776p5222nm638/. , Coding and cryptography (international workshop, WCC 2005, Bergen, Norway, March 14–18, 2005)
  4. ^ a b c d e Cooke, C (1999). "Polynomial construction of complex Hadamard matrices with cyclic core"]. Applied Mathematics Letters 12: 87–93. doi:10.1016/S0893-9659(98)00131-1. http://www.springerlink.com/content/d81776p5222nm638/. 
  5. ^ J. Adamek (1991). Foundations of Coding. New York: John Wiley. 
  6. ^ Zierler, N. (1959). "Linear recurring sequences". J. Soc. Indust. Appl. Math. 7: 31–48. doi:10.1137/0107003. 
  7. ^ The Vienna RNA secondary structure package

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Nucleic acid design — can be used to create nucleic acid complexes with complicated secondary structures such as this four arm junction. These four strands associate into this structure because it maximizes the number of correct base pairs, with A s matched to T s and …   Wikipedia

  • DNA nanotechnology — seeks to make artificial, designed nanostructures out of nucleic acids, such as this DNA tetrahedron.[1] Each edge of the tetrahedron is a 20 base pair DNA double helix, and each vertex is a three arm junction. DNA n …   Wikipedia

  • evolution — evolutional, adj. evolutionally, adv. /ev euh looh sheuhn/ or, esp. Brit., /ee veuh /, n. 1. any process of formation or growth; development: the evolution of a language; the evolution of the airplane. 2. a product of such development; something… …   Universalium

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

  • Список награждённых Национальной медалью науки США — Джошуа Ледерберг (справа) получает Национальную медаль науки из рук Президента США Джорджа Буша старшего Список …   Википедия

  • Bioinformatics — For the journal, see Bioinformatics (journal). Map of the human X chromosome (from the NCBI website). Assembly of the human genome is one of the greatest achievements of bioinformatics. Bioinformatics …   Wikipedia

  • Nobel Prizes — ▪ 2009 Introduction Prize for Peace       The 2008 Nobel Prize for Peace was awarded to Martti Ahtisaari, former president (1994–2000) of Finland, for his work over more than 30 years in settling international disputes, many involving ethnic,… …   Universalium

  • Evolution — This article is about evolution in biology. For other uses, see Evolution (disambiguation). For a generally accessible and less technical introduction to the topic, see Introduction to evolution. Part of a series on …   Wikipedia

  • RNA interference — (RNAi) is a mechanism that inhibits gene expression at the stage of translation or by hindering the transcription of specific genes. RNAi targets include RNA from viruses and transposons (significant for some forms of innate immune response), and …   Wikipedia

  • chemistry — /kem euh stree/, n., pl. chemistries. 1. the science that deals with the composition and properties of substances and various elementary forms of matter. Cf. element (def. 2). 2. chemical properties, reactions, phenomena, etc.: the chemistry of… …   Universalium