BIOLOGICAL INSPIRATION FOR COMPUTING 281
a digital code, particular strands of DNA can be used to code information, and in particular, joinings
and other recombinations of these strands can be used to represent putative solutions to certain compu-
tational problems.
This idea is known variously as DNA computation, molecular computation, and biomolecular
computation (BMC). The use of DNA as a computational system had been discussed theoretically by T.
Head in 1987,^104 but the idea leapt into prominence with Len Adleman’s publication in 1994 of a
working experiment (Box 8.3) that solved a seven-node instance of the Hamiltonian path problem, an
NP-complete problem that is a special case of the Traveling Salesman Problem.^105
8.4.1.1 Description
Early attention has focused on DNA because its properties are extremely attractive as a basis for a
computational system. First, it offers a digital abstraction: the value of a piece of DNA can be precisely
and only A, G, T, or C. This abstraction is of course quite familiar to the digital abstractions of 0 and 1.
Second, the Watson-Crick complementarity of the bases (A with T, G with C) allows matching opera-
tions, conceptually similar to “if” clauses in programming. Third, DNA’s construction as a string allows
a number of useful operations such as insertion, concatenation, deletion, and appending. Next, billions
of years of evolution have provided a large set of enzymes and other molecules that perform those
operations, some in very specific circumstances. Finally, the last few decades of progress in molecular
biology have created a laboratory and instrument infrastructure for the manipulation and analysis of
DNA, such as the custom synthesis of sequences of DNA, chips that can detect the presence of indi-
vidual sequences, and techniques such as polymerase chain reaction (PCR) that can amplify existing
sequences. Without such an infrastructure (importantly including the existence of a body of trained
laboratory technicians), the use of DNA for computation would be entirely theoretical.
Biomolecular computing provides a number of advantages that make it quite attractive as a poten-
tial base for computation. Most obvious are its information density, about 10^21 bits per gram (billions of
times more dense than magnetic tape), and its massive parallelism, 10^15 or 10^16 operations per sec-
ond.^106 Less immediately apparent, but of equal potential importance, is its energy efficiency: it uses
approximately 10–19 joules per operation, close to the information theoretic limit (compared to 10–9
joules per operation for silicon).
One class of biomolecular computing generates witness molecules for all possible solutions to a
problem and then uses molecular selection to sift out molecules that represent solutions to the problem
at hand. This was the basic architecture developed by Adleman (described in Box 8.3), and with an
exponential amount of witness material, this approach can theoretically solve NP-complete problems.
Short sequences of DNA (or RNA) are used to represent data, and these are combined to form longer
strands, each of which represents a potential solution. Obtaining the particular DNA strand that repre-
sents the solution is thus based on laboratory processes that extract the proper DNA strand, and these
laboratory processes are based on the existence of an algorithm that can distinguish between correct and
incorrect solutions.
A further important step was taken in 2001 by Benenson et al., who developed a programmable
finite automaton comprising DNA and DNA-manipulating enzymes that solves certain computational
problems autonomously.^107 In particular, the automaton’s “hardware” consisted of a restriction nu-
(^104) T. Head, “Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors,”
Bulletin of Mathematical Biology 49(6):737-759, 1987.
(^105) L.M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science 266(5187):1021-1024, 1994.
(^106) It is only the fact of massive parallelism that makes biological computing at all feasible, because biological switching speeds
are diffusion-limited and quite slow.
(^107) Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro, “Programmable and Autonomous Computing
Machine Made of Biomolecules,” Nature 414(6862):430-434, 2001.