Glimpse from the top : DNA Computation


Since the invention of conventional register based computational units which has rooted most of our
modern day machines’ computing units, there have been searches for other information holding 
mediums which can be the candidates for more powerful computational systems. These searches have 
not been in vain. Today we have two mainstream emerging alternate computational theories,
namely Quantum Computation and DNA Computation. Quantum Computation aims to exploit the 
fact that although quantum states are not directly observable, they have the capacity to contain a 
vast amount of information. A quantum bit in contrast to a classical bit can contain much more
information than 0 or 1 because of quantum superposition. An optimal Quantum algorithm for a ‘nee-
-dle in haystack search’ can be proved to take O(sqrt(n)) [Grover] computations at worst, whereas no 
classical algorithm can do better than O(n). But handling a quantum bit to perform computation requ-
-ires very sophisticated technology that becomes a big barrier to commercialization. Similarly, the idea
 of DNA Computation arises from the innate capacity of DNA molecules to store a vast amount of inform-
-ation in a very small space. A 3 billion length DNA can encode information of 4^(3 billion) varieties and can
 be stored in the size of a nucleus! Example: Every human cell. This makes DNA a prime target for carrying 
information in biomolecular computing research and hence the motivation for pursuing DNA Computat-
-ion. Next, we elaborate on a plausible theory of computation using DNA as an information carrier, its im-
-plementational plausibility, drawbacks, and scopes of improvement.

Advances in DNA Computation( A Literary View)

Need for DNA Computation: Silicon microprocessor has been at the heart of computing
for several decades. In that time manufacturers have put more and more electronic devices
onto their microprocessors. According to Moore’s Law, the number of electronic devices put
on a microprocessor has doubled every 18 months. Many have predicted that Moore’s Law,
will reach saturation, because of the physical speed and miniaturization limitations of silicon
microprocessors. At the same time, DNA Computing does not limit with Moore’s law because
DNA is a very small chemical molecule so we can massively parallelize the computations done
with DNA molecules.

DNA Logic Gates: Logic gates are basic computational units that are required to be designed in
any form of computational theory.  The DNA logic gates use DNA strands instead of electrical
signals to perform logical operations. They take fragments of genetic materials as input and
output a single fragment by joining them together. For example, a genetic “And gate” joins
two DNA inputs end to end by chemically binding them together. These logic gates can also be
combined with DNA microchips and used in various different ways. This would be especially
useful in the field of Biomedical Engineering.

The [algorithm] presented here can be used to simulate any DNA based combinational boolean
operator. We need to know the truth table of the corresponding operations used. Inputs to the
logic gates are provided in the form of molecular beacons(MB) whose fluorescence is used for
detection. Each variable used here is represented as a unique oligonucleotide sequence. We
then go through each row of the truth table and if the output is ‘0’, then we use the
complementary sequence of the variables and if the output is ‘1’, then we use the original
sequence itself. The inputs provided undergo self-hybridization. Output can be decided as
follows: if the input sequence doesn’t find its complementary sequence no hybridization in
MB(input) occurs and hence remains dark which means the output is ‘0’. On the other hand,
illumination occurs if it is able to find its complement because of the opening of the loop
structure in MB which means the output is ‘1’. The hybridization strands can again be used
after they are denatured.

Prospects in solving NP-HARD problems: Theoretically each DNA molecule can process
data parallelly, hence it is possible to process all potential solutions of NP-Hard problems parallelly and
search through them. In 1994 Prof. LM Adleman performed an [experiment] that surprised the entire
community. He solved Hamiltonian path problem (one of the NP-Hard problems which take
exponential time to solve) using DNA computing where Graph (input) was encoded as
oligonucleotides and operations were performed using molecular biology tools. The basic structure of
experiment was as follows:-
1. They took n oligonucleotides of length 20 base pairs (bps).

2. They ligated all the strands in a random manner inside a test tube. This step was done for
both sense and antisense strands. This step generated DNA strands of variable lengths, and if there
exists a Hamiltonian path that sequence strand corresponding the path will be present with very
high probability.

3. Now they did PCR amplification reaction using primer against the oligonucleotide Vin and Vout.  
This step amplified only those strands which had oligonucleotide sequence corresponding to Vin and

4. Now they separated all the strands amplified in step 3 by running the whole mixture on an agarose
gel. This gave them all the paths from Vin to Vout of length n-1.

5. Now using magnetic bead separation we separate all those strands which contain all the vertices.
After all these processes if there is any path left then accept.

Present State and Future Prospects of DNA Computers: Weizmann Institute of Science
in Rehovot, Israel developed a programmable DNA computer which can perform 330 trillion
per second. The difference between silicon-based PC and DNA Computer is that silicon-based PC’s
focus on speed per instruction while DNA computer focuses on parallelism. This makes DNA
computers more suitable for problems with multiple solutions. In future, we may see hybrid computers
with both DNA and silicon processors, which on need can switch. Most of the latest research tries to
solve the problem of numerical value representation, there are multiple ways of representing
numerical value but it’s still an open problem to find the optimal representation. DNA computing
shows great promise and in future might be very suitable for image processing and cryptography
related tasks.

Current Limitations:
Apart from the fact that using DNA computers are much more complex than the normal
computers we actually use, there are a few other limitations as well. The first one is the
problem of generating ‘solution sets’, which essentially correspond to creating DNA strands.
Even the most trivial of general computing problems would require a large number of DNA
strands. The second problem arises from the methodology that DNA computing uses - from
performing bio-molecular operations in a controlled manner to actually encoding the 
errors and uncertainties creep in. Also, every ‘right’ path to the correct answer is accompanied
by millions of incorrect paths. Also, from the point of view of computability theory, DNA
computation doesn’t offer significant improvement over traditional method, especially if
the parallelism is not implicit in the problem.


DNA computation generates a complete set of potential solutions and can handle very large
amounts of data efficiently. Due to the availability of large reserves of genetic material, it is
not expensive to build them. There is a distinct memory block for encoding bits which is to
our advantage. But, even for some relatively simple problems, it may require large amounts
of memory. There are many technological challenges remaining before we can use DNA
computing widely. But with the rapidly improving technology, we can expect some new
techniques to be developed which will reduce the computational errors produced by some
unwanted chemical reactions.


I am thankful to my friends Ankit Salvi, Harshit Kr. Sinha, Abhinay Natti and Sanket for
helping in writing this article.