BIOLOGICAL INSPIRATION FOR COMPUTING 285
scene) and, in massively parallel fashion, identify potential matches. This idea could even be extended
to queries of proteins or chemicals, if the appropriate query strand of DNA can be generated.
A separate approach to biomolecular memory uses changes in the sequence of individual strands to
represent bits. Certain enzymes known as site-specific recombinases (SSRs) can (among a set of other
potential modifications) reverse the sequence of the bases between two marker sequences; repeated
application of such an enzyme would flip the sequence back and forth, representing 0 and 1. In this
implementation, a single bit requires a long series of bases; research aims at attaining the far more dense
use of single bases as bits (in fact, as two bits, since each base can have four values).
8.4.1.3 Challenges
Biomolecular computing faces some significant challenges to adoption beyond the laboratory. The
most cited barrier is the exponential doubling of the volume of DNA required to perform exhaustive
search of NP-complete problems, such as done by Adleman (Section 8.4.1.1). That is, while the number
of different DNA sequences required grows linearly with the number of directed paths in a graph, the
volume of those DNA sequences needed to solve a given problem is exponential in the problem’s size
(in this case, the number of nodes in the graph). Put differently, for the problems to which DNA
computing is applicable, a problem that can be solved in exponential time on silicon-based von
Neumann computers is replaced by one that can be solved with exponential increases of mass. It is thus
an open question today about what kinds of problems can be solved practically using DNA computing.
For example, Hartmanis reports that the amount of DNA necessary to replicate Adleman’s experiment
for a 200-node problem would exceed the weight of the Earth.^112
While this is a valid concern, standard computers have been widely accepted despite their inability
to solve NP-complete problems in a timely fashion. To the best understanding of computer science
today, NP-complete problems are fundamentally challenging, and so it ought to be no surprise that
even new models of computation struggle with them. Nevertheless some breakthrough may provide
subexponential scaling for biomolecular-based exhaustive search.
A second concern involves the time-consuming and expensive laboratory techniques necessary to
set up and read out the answer from an experiment—in essence, the input-output problem for bio-
molecular computing. While DNA reactions themselves offer staggering parallelism (although in fact
they take about an hour), the bottleneck may be the time it takes for trained humans to undertake the
experiment. Adleman’s experiment required about 7 days of laboratory work. And although DNA
synthesis itself is cheap, some of the enzymes used in Adleman’s experiments cost 10,000 times as much
as gold,^113 suggesting that scaling up significantly may not be feasible on economic grounds.
Related to this is the fact that DNA computation is not error-free. Synthesis of sequences can
introduce errors; strands of DNA that are close to being complements—but not quite—may still hybrid-
ize; point mutations may occur; sheer chance may allow strands of DNA to escape enzymatic destruc-
tion; and so forth. Although comparatively high error rates can be acceptable in laboratory environ-
ments, this is far more problematic for computation. The problem can be ameliorated partly by the use
of techniques familiar to communications protocols, including error-correcting codes and careful design
of the code words used in computation, so as to maximize the information distance between any pair.
This last example is a good case of computer science and biological cooperation: the distance between a
pair of code words composed of a series of bases is a product of both its information content and its
biochemical properties. Word design is currently an active area of DNA computation research.
(^112) J. Hartmanis, “On the Weight of Computations,” Bulletin of the European Association for Theoretical Computer Science 55:136-
138, 1995.
(^113) A.L. Delcher, L. Hood, and R.M. Karp, “Report on the DNA/Biomolecular Computing Workshop (June 6-7, 1996),” Na-
tional Science Foundation, NSF 97-168, 1998, available at http://www.nsf.gov/pubs/1998/nsf97168/nsf97168.htm.