Coding theory approaches to nucleic acid design

Let ${\displaystyle {\mathit {C_{p}}}=\left\{1,x,x^{2},\ldots ,x^{p-1}\right\}}$ be the cyclic group generated by ${\displaystyle {\mathit {x}}}$, where ${\displaystyle x=\exp(2\pi ij/p)}$ is a complex primitive ${\displaystyle p}$th root of unity, and ${\displaystyle p>2}$ is a fixed prime. Further, let ${\displaystyle {\mathit {A}}=(x^{a_{i}})}$, ${\displaystyle {\mathit {B}}=(x^{b_{i}})}$ denote arbitrary vectors over ${\displaystyle \mathbb {C} _{p}}$ which are of length ${\displaystyle {\mathit {N}}=pt}$, where ${\displaystyle {\mathit {t}}}$ is a positive integer. Define the collection of differences between exponents ${\displaystyle {\mathit {Q}}=\{a_{i}-b_{i}\mod p:i=1,2,\ldots ,N\}}$, where ${\displaystyle {\mathit {n_{q}}}}$ is the multiplicity of element ${\displaystyle {\mathit {q}}}$ of ${\displaystyle {\text{GF}}(p)}$ which appears in ${\displaystyle {\mathit {Q}}}$.[4]

Vector ${\displaystyle {\mathit {Q}}}$ is said to satisfy Property U if and only if each element ${\displaystyle {\mathit {q}}}$ of ${\displaystyle {\text{GF}}(p)}$ appears in ${\displaystyle {\mathit {Q}}}$ exactly ${\displaystyle {\mathit {t}}}$ times (${\displaystyle {\mathit {n_{q}}}=t,q=0,1,\ldots ,p-1}$)

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

Lemma. Orthogonality of vectors over ${\displaystyle {\mathit {C_{p}}}}$ – For fixed primes ${\displaystyle {\mathit {p}}}$, arbitrary vectors ${\displaystyle {\mathit {A}},{\mathit {B}}}$ of length ${\displaystyle {\mathit {N}}=pt}$, whose elements are from ${\displaystyle {\mathit {C_{p}}}}$, are orthogonal if the vector ${\displaystyle {\mathit {Q}}}$ satisfies Property U, where ${\displaystyle {\mathit {Q}}}$ is the collection of differences ${\displaystyle \mod {\mathit {p}}}$ between the Hadamard exponents associated with ${\displaystyle {\mathit {A}},{\mathit {B}}}$.

Let ${\displaystyle {\mathit {V}}}$ be an arbitrary vector of length ${\displaystyle {\mathit {N}}}$ whose elements are in the finite field ${\displaystyle {\text{GF}}(p)}$, where ${\displaystyle p}$ is a prime. Let the elements of a vector ${\displaystyle V}$ constitute the first period of an infinite sequence ${\displaystyle a(V)}$ which is periodic of period ${\displaystyle N}$. If ${\displaystyle N}$ 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 ${\displaystyle N}$ elements. If whenever the elements of ${\displaystyle V}$ are permuted arbitrarily to yield ${\displaystyle V^{*}}$, the sequence ${\displaystyle a(V^{*})}$ is an M-sequence, then the sequence ${\displaystyle a(V)}$ 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 ${\displaystyle {\mathit {E}}={\mathit {E_{c}}}}$ whose elements are in Galois field ${\displaystyle {\text{GF}}(p)}$ and whose dimension is ${\displaystyle N=p^{n}-1}$. The rows of ${\displaystyle {\mathit {E}}}$ will be the nonzero codewords of a linear cyclic code ${\displaystyle K}$, if and only if there is polynomial ${\displaystyle g(x)}$ with coefficients in ${\displaystyle \mathrm {GF} (p)}$, which is a proper divisor of ${\displaystyle {\mathit {x^{N}-1}}}$ and which generates ${\displaystyle K}$. In order to have${\displaystyle N}$ nonzero codewords, ${\displaystyle g(x)}$ must be of degree ${\displaystyle N-n}$. Further, in order to generate a cyclic Hadamard core, the vector (of coefficients of) ${\displaystyle g(x)}$ when operated upon with the cyclic shift operation must be of period ${\displaystyle N}$, and the vector difference of two arbitrary rows of ${\displaystyle {\mathit {E}}}$ (augmented with zero) must satisfy the uniformity condition of Butson,[5] previously referred to as Property U. One necessary condition for ${\displaystyle N}$-periodicity is that ${\displaystyle x^{N}-1=g(x)h(x)}$, where ${\displaystyle 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 ${\displaystyle [0,g(x)]}$ are uniformly distributed over ${\displaystyle {\text{GF}}(p)}$, i.e. each residue ${\displaystyle 0,1,\ldots ,p-1}$ appears the same number of times (Property U). A proof that this heuristic approach always produces a cyclic core is given below.

Consider a monic irreducible polynomial ${\displaystyle h(x)}$ over ${\displaystyle {\text{GF}}(p)}$ of degree ${\displaystyle {\mathit {n}}}$ having a suitable companion ${\displaystyle g(x)}$ of degree ${\displaystyle N-n}$ such that ${\displaystyle g(x)h(x)=x^{N}-1}$, where the vector ${\displaystyle [0,g(x)]}$ satisfies Property U. This requires only a simple computer algorithm for long division over ${\displaystyle {\text{GF}}(p)}$. Since ${\displaystyle h(x)|x^{N}-1}$, the ideal generated by ${\displaystyle g(x)\mod (x^{N}-1)}$ is a cyclic code ${\displaystyle {\mathit {K}}}$. Moreover, Property U guarantees the nonzero codewords form a cyclic matrix, each row of period ${\displaystyle N}$ under cyclic permutation, which serves as a cyclic core for the Hadamard matrix ${\displaystyle H(p,pn)}$. As an example, a cyclic core for ${\displaystyle H(3,9)}$ results from the companions ${\displaystyle h(x)=x^{2}+x+2}$ and ${\displaystyle g(x)=x^{6}+2x^{5}+2x^{4}+2x^{2}+x+1}$. The coefficients of ${\displaystyle g}$ indicate that ${\displaystyle \{0,1,6\}}$ is the relative difference set, ${\displaystyle \mod 8}$.

Let ${\displaystyle {\mathit {p}}}$ be a prime and ${\displaystyle {\mathit {N}}+1={\mathit {pn}}}$, with ${\displaystyle {\mathit {g}}(x)}$ a monic polynomial of degree ${\displaystyle {\mathit {N}}-{\mathit {n}}}$ whose extended vector of coefficients ${\displaystyle C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1}]}$ are elements of ${\displaystyle {\text{GF}}(p)}$. Suppose the following conditions hold:

1. vector ${\displaystyle C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\dots ,{\mathit {c}}_{N-1}]}$ satisfies the property U, and
2. ${\displaystyle g(x)h(x)=x^{N}-1}$, where ${\displaystyle h(x)}$ is a monic irreducible polynomial of degree ${\displaystyle n}$.

Then there exists a p-ary linear cyclic code ${\displaystyle {\bar {K}}}$ of blocksize ${\displaystyle N}$, such that the augmented code ${\displaystyle K=[0,{\bar {K}}]}$ is the exponent matrix for the Hadamard matrix ${\displaystyle H(p,p_{n})=xK}$, with ${\displaystyle x=e^{2\pi i/p}}$, where the core of ${\displaystyle H}$ is a cyclic matrix.

Proof:

First note that ${\displaystyle g(x)}$ is monic and divides ${\displaystyle x^{N}-1}$ with degree ${\displaystyle N-n}$. Now, we need to show that the matrix ${\displaystyle E_{c}}$ whose rows are nonzero codewords constitutes a cyclic core for some complex Hadamard matrix ${\displaystyle H}$.

Given that ${\displaystyle {\mathit {C}}}$ satisfies property U, all of the nonzero residues of ${\displaystyle {\text{GF}}(p)}$ lie in C. By cyclically permuting elements of ${\displaystyle C}$, we get the desired exponent matrix ${\displaystyle {E_{c}}}$ where we can get every codeword in ${\displaystyle {E_{c}}}$ by permuting the first codeword. (This is because the sequence obtained by cyclically permuting ${\displaystyle C}$ is M-invariant.)

We also see that augmentation of each codeword of ${\displaystyle {E_{c}}}$ by adding a leading zero element produces a vector which satisfies Property U. Also, since the code is linear, the ${\displaystyle \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 ${\displaystyle {\mathit {K}}}$ form a Hadamard exponent. Thus, ${\displaystyle {\mathit {xK}}}$ is the standard form of some complex Hadamard matrix ${\displaystyle {\mathit {H}}}$.

Thus from the above property, we see that the core of ${\displaystyle {\mathit {E}}}$ is a circulant matrix consisting of all the ${\displaystyle N={\mathit {p}}^{k}-1}$ cyclic shifts of its first row. Such a core is called a cyclic core where in each element of ${\displaystyle \mathbb {Z} _{p}}$ appears in each row of ${\displaystyle {\mathit {E}}}$ exactly ${\displaystyle (N+1)/p={\mathit {p}}^{k-1}}$ times, and the Hamming distance between any two rows is exactly ${\displaystyle (N+1)(p-1)/p=(p-1)p^{k-1}}$. The ${\displaystyle {\mathit {N}}}$ rows of the core ${\displaystyle {\mathit {E}}}$ form a constant-composition code - one consisting of ${\displaystyle {\mathit {N}}}$ cyclic shifts of some length ${\displaystyle {\mathit {N}}}$ over the set ${\displaystyle \mathbb {Z} _{p}}$. Hamming distance between any two codewords in ${\displaystyle \mathbb {Z} _{p}}$ is ${\displaystyle (p-1){\mathit {p}}^{k-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 ${\displaystyle {\mathit {N}}={\mathit {p}}^{\mathit {k}}-1}$ for ${\displaystyle {p}}$ prime and ${\displaystyle {k}\in \mathbb {Z} ^{+}}$. Let ${\displaystyle g(x)=c_{0}+c_{1}x+c_{2}x^{2}+\dots +c_{N-k}x^{N-k}}$ be a monic polynomial over ${\displaystyle \mathbb {Z} _{p}}$, of degree N − k such that ${\displaystyle {\mathit {g}}({\mathit {x}}){\mathit {h}}({\mathit {x}})={\mathit {x}}^{N}-1}$ over ${\displaystyle \mathbb {Z} _{p}}$, for some monic irreducible polynomial ${\displaystyle {\mathit {h}}({\mathit {x}})\in \mathbb {Z} _{p}[{\mathit {x}}]}$. Suppose that the vector ${\displaystyle ({c}_{0},{c}_{1},\ldots ,{c}_{N-k},{c}_{N-k+1},\ldots ,{c}_{N-1})}$, with ${\displaystyle {\mathit {c}}_{i}=0}$ for (N − k) < i < N, has the property that it contains each element of ${\displaystyle \mathbb {Z} _{p}}$ the same number of times. Then, the ${\displaystyle {\mathit {N}}}$ cyclic shifts of the vector ${\displaystyle {\mathit {g}}=({\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-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 ${\displaystyle \mathbb {Z} _{p}}$ by mapping the symbols of ${\displaystyle \mathbb {Z} _{p}}$ to the symbols of the DNA alphabet, ${\displaystyle {\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}}$. For example, using cyclic constant composition code of length ${\displaystyle {\mathit {3}}^{k}-1}$ over ${\displaystyle \mathbb {Z} _{3}}$ guaranteed by the theorem proved above and the resulting property, and using the mapping that takes ${\displaystyle 0}$ to ${\displaystyle {\mathit {A}}}$, ${\displaystyle 1}$ to ${\displaystyle {\mathit {T}}}$ and ${\displaystyle 2}$ to ${\displaystyle {\mathit {G}}}$, we obtain a DNA code ${\displaystyle {\mathcal {D}}}$ with ${\displaystyle {\mathit {3}}^{k}-1}$ and a GC-content of ${\displaystyle {\mathit {3}}^{k-1}}$. Clearly ${\displaystyle {\mathit {d_{H}}}=2.{\mathit {3}}^{k-1}}$ and in fact since ${\displaystyle {\mathit {\bar {G}}}={\mathit {C}}}$ and no codeword in ${\displaystyle {\mathcal {D}}}$ contains no symbol ${\displaystyle {\mathit {C}}}$, we also have ${\displaystyle {\mathit {d}}_{H}^{RC}({\mathcal {D}})\geq 3^{k-1}}$. This is summarized in the following corollary.[4]

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

Each of the following vectors generates a cyclic core of a Hadamard matrix ${\displaystyle H(p,p^{n})}$ (where ${\displaystyle {\mathit {N}}+1={\mathit {p^{n}}}}$, and ${\displaystyle {\mathit {n}}=3}$ in this example):[4]

${\displaystyle g^{(1)}=(22201221202001110211210200)}$;

${\displaystyle g^{(2)}=(20212210222001012112011100)}$.

Where, ${\displaystyle {g(x)}=a_{0}+a_{1}x+\dots +a_{n}x^{n}}$.

Thus, we see how DNA codes can be obtained from such generators by mapping ${\displaystyle {0,1,2}}$ onto ${\displaystyle {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 ${\displaystyle {g^{(1)}}}$ via the mapping ${\displaystyle 0-A;1-T;2-G}$, while the codeword ${\displaystyle {g^{(2)}}}$ was obtained from the same generator ${\displaystyle {g^{(1)}}}$ via the mapping ${\displaystyle 0-G;1-T;2-A}$.

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 ${\displaystyle {\mathcal {Q}}}$ onto the set of 2-bit length binary words as shown: ${\displaystyle {\mathit {A}}\to 00}$, ${\displaystyle {\mathit {T}}\to 01}$, ${\displaystyle {\mathit {C}}\to 10}$, ${\displaystyle {\mathit {G}}\to 11}$.

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

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

Now, let ${\displaystyle b(q)={\mathit {b}}_{0}{\mathit {b}}_{1}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-1}}$.

Now, let the subsequence ${\displaystyle e(q)={\mathit {b}}_{0}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-2}}$ be called the even subsequence of ${\displaystyle {b(q)}}$, and ${\displaystyle o(q)={\mathit {b}}_{1}{\mathit {b}}_{3}{\mathit {b}}_{5}\ldots {\mathit {b}}_{2n-1}}$ be called the odd subsequence of ${\displaystyle {b(q)}}$.

Thus, for example, for ${\displaystyle q=ACGTCC}$, then, ${\displaystyle b(q)=001011011010}$.

Then ${\displaystyle e(q)=011011}$ and ${\displaystyle o(q)=001100}$.

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

From this choice of binary mapping, the GC-content of DNA sequence ${\displaystyle {\mathit {q}}}$ = Hamming weight of ${\displaystyle {e(q)}}$.

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

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

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

${\displaystyle {\mathcal {E}}=\left\{a{\bar {b}}:a,b\in {\mathcal {B}}_{w}\right\}}$, ${\displaystyle {\mathcal {O}}=\left\{ab^{RC}:a,b\in {\mathcal {B}},a<_{lex}b\right\}}$.

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

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

Furthermore, ${\displaystyle {\mathit {d_{H}}}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})}$ and ${\displaystyle {\mathit {d_{H}}}^{R}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})}$ ( this is because ${\displaystyle {\mathcal {B}}_{w}}$ is a subset of the codewords in ${\displaystyle {\mathcal {B}}}$).

Also, ${\displaystyle {\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 ${\displaystyle b}$ and ${\displaystyle d}$ both have weight ${\displaystyle {\mathit {w}}}$. This implies that ${\displaystyle b^{RC}}$ and ${\displaystyle d^{RC}}$ have weight ${\displaystyle {\mathit {n-w}}}$.

And due to the weight constraint on ${\displaystyle {\mathit {w}}}$, we must have for all ${\displaystyle a,b,c,d\in {\mathcal {B}}_{w}}$, ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}}$ has ${\displaystyle M(M-1)/2}$ codewords of length ${\displaystyle 2n}$.

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

Similarly, ${\displaystyle {d_{H}^{RC}}(({\mathcal {O}}))\geq {d_{\min }}}$.

Therefore, the DNA code

${\displaystyle {\mathcal {C}}=\bigcup _{w=d_{\min }}^{w_{\max }}{\mathcal {C}}_{w}}$

with ${\displaystyle {w_{\max }}=({n}-\lceil d_{\min }/2\rceil )/2}$, has ${\displaystyle {\frac {1}{2}}M(M-1)\sum _{w=d_{\min }}^{w_{\max }}\left\vert {A_{w}}^{2}\right\vert }$ codewords of length ${\displaystyle 2{\mathit {n}}}$, and satisfies ${\displaystyle {\mathit {d_{H}}}({\mathcal {B}})\geq {\mathit {d_{\min }}}}$ and ${\displaystyle {\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.