22-05-2014, 03:32 PM
DNA computing--promises, problems and perspective
1370274391-00645835.pdf (Size: 511.34 KB / Downloads: 115)
Recently, extensive interest
has been expressed in possi-
bly using DNA (or other
biological macromolecules)
as computing hardware. We will
briefly examine the possibilities
DNA computing and general molecu-
lar computation open up and the
problems faced in achieving them.
Finally, we will try to put them in a
broader perspective
Calculating Using DNA
DNA carries the genetic informa-
tion for life as we know it. Before its
identification by Watson and Crick
in 1953, the quantum physicist
Schrodinger had already accurately
predicted the carrier of genetic infor-
mation to be an “aperiodic crystal”: a
structured medium (crystal) capable
of storing information because of
variation allowed within the structure
(aperiodicity) . Since Watson and Crick’s discov-
ery, many ways to manipulate DNA
have been found and developed. Bio-
logical techniques include the use of
enzymes for cutting and pasting, and
the polymerase chain reaction for
reproducing DNA strands. Biotechno-
logical techniques include selective
filtering, tagging and DNA sequenc-
ing. Together, these developments
enable us to use DNA as a modifiable
storage medium, a kind of memory.
These developments also allow us to
use these techniques as operations on
that memory to implement algorithms.
DNA was first used for computa-
tions in 1994. In his ground breaking
Science article, Leonard Adleman
described his experiment that solved a
seven-node instance of the Hamilton-
ian path problem from graph theory.
(The problem is finding a path through a mathematical graph that contains all
nodes exactly once.) He devised an
encoding for edges in a graph based on encodings of their nodes
Using this technique, Adleman
could produce sequences correspond-
ing to candidate solution paths by
randomly gluing together sequences
for single nodes. By producing
enough of such sequences, all candi-
date solutions would be constructed.
This construction was done in paral-
lel. (All strands underwent the reactions simultaneously.)
By a sequence of filtering steps,
strands that were the wrong length or
did not contain node one, two,
etcetera were eliminated. Only strands
that corresponded to actual solutions
were kept. This filtering also was
done concurrently on all strands. The
fact that DNA remained after this
process indicated that solutions to the
problem existed; by sequencing the
remaining DNA, a single solution
could be read out
This feat has shown the feasibilityof doing special-purpose computa-
tions using DNA. The novelty was
not in the algorithm, nor in the speed.
(One can easily solve the problem
much faster by hand.) But, in the fact,
that the implementation used biotech-
nology, which hitherto had never
been used as computing hardware.
Also, it exploited the potential for
parallelism in this medium.
Genaral purpose DNA computing
In his article, Adleman posed the
question whether a universal DNA
computing scheme could exist. Not
long afterwards, other researchers
answered that question. They showed
via a number of different approaches
that, at least theoretically, DNA com-
puting can be universal. DNA based
computing machines need not be lim-
ited to specific tasks; they can be programmed like the electronic computers we are used to
These proofs amount to showing
how a DNA computing scheme can
simulate a well-known universal model
of computation. For example, it could
simulate a universal Turing machine.
[This is a mathematical abstraction of a
sequential computer. a finite control
automaton (“program”) operating on a
potentially infinite tape (“memory.”)]
Or it could simulate a universal cellular
automaton. [This is a potentially infinite
grid of cells (finite state automata) com-
municating with their neighbors and
operating in parallel.)]
For example, a strand of DNA can
be viewed as encoding the contents of
a Turing machine tape Rewriting this
tape, according to the rules in the
finite control of the machine, can be
done via a sophisticated scheme of
enzymatic reactions.
Keep in mind, these proofs are theo-
retical. They merely show that the theo-
ry poses no objections to full-blown
DNA computers. However, most of
these proofs make assumptions that are
not realistic from a practical viewpoint,
such as error-free operations. They are,
therefore, not directly applicable to
engineering a DNA computer. Also,
most of them do not seem to exploit the
parallelism in DNA reactions very well.
However, these proofs do illustrate
that there are many possible architec-
tures for DNA computers Thus, one
should be careful when generalizing
observations about a particular architec-
ture or method of DNA computing to
the whole field.