284 CATALYZING INQUIRY
presence of DNA polymerase and DNA ligase, the rewrite rules cause new DNA molecules to be
produced that represent intermediate states in a computation. These new DNA molecules can be a very
general function of the beginning mixture of DNA molecules, and a DNA encoding has been discovered
that permits such a system to theoretically implement arbitrary computation.
8.4.1.2 Potential Application Domains
The field of biomolecular computing is still composed of theory and tentative laboratory steps; we
are years away from commercial activity. The results of laboratory experiments are proofs of concept; as
yet, no biomolecular computer has outperformed an electronic computer.
Biomolecular computing is, in principle, well suited for problems that involve “brute force” solu-
tions, in which candidate solutions can be tested individually to see if they are correct. As noted above,
the main application pursued for the first decade of biomolecular computing work is the exhaustive
solution of NP-complete problems. While this has been successful for small numbers of nodes (up to 20),
the fact that it requires exponential volumes of DNA most likely limits the further development of NP-
solving systems (see below for further discussion).
Biomolecular computation also has potential value in the field of cryptography. For example, DNA,
with its incredible information density, could serve as an ideal one-time pad, as a tiny sample could
provide petabytes of data suitable for use for encryption (as long as it was suitably random). More
generally, biomolecules could serve as components of a larger computational system, possibly serving
alongside traditional silicon-based semiconductors. For this, and indeed any biomolecular computing
system, a challenge is the transformation of information from digital representation into biomolecules
and back again. Traditional molecular biological engineering has provided a number of tools for synthe-
sizing DNA sequences and reading them out; however, these tend to be fairly lengthy processes. Recent
advances in DNA chips show the potential for more efficient biodigital interfaces. For example, photo-
sensitive chips will synthesize given sequences of DNA based on optical inputs and, similarly, will
produce optical signals in the presence of certain sequences. These optical signals are two-dimensional
arrays of intensities that can be read by digital image-processing hardware and software. Other ap-
proaches for output include the inclusion of fluorescent materials in the DNA molecules or other
additives that can be detected with the use of microscopy.
A potential component role for biomolecules is as memory. Whereas biomolecular computation
must compete against rapidly improving and increasingly parallel optoelectronic technologies for com-
putation, biomolecular memory is many orders of magnitude superior to conventional magnetic imple-
mentations in terms of density. Although DNA memory is unlikely to be used as the rapid-access read-
write memory of modern computers, its density makes it useful for “black-box” applications that write
a great deal of data, but read only on rare occasions (a fact that would usually tend to increase the
acceptable retrieval time).
One such implementation would use DNA as the storage medium of an associative database. A
DNA strand would encode the information of a specific record, with sequences on that strand repre-
senting attributes of the record and a unique index. Query strings would be composed of the comple-
ment of the desired attribute. Although individual lookups would be slow (limited by the speed of
DNA chemistry), the total amount of information stored would be enormous and the queries would
execute in parallel over the entire database. In contrast, conventional electronic computer implementa-
tions of associative memory require linear time with the size of the database.
Such a DNA database might be most useful as a set of tools to manipulate, retrieve, or analyze
existing biological or chemical substances. For example, special-purpose DNA computers might search
through databases of genetic material. In this model, a large library of genetic material (perhaps repre-
senting DNA sequences of various biological lineages, or of criminals) would be stored in its original
DNA form, rather than as an electronic digital representation. Biomolecular computers would generate
appropriate strands representing a query (matching a sequence found in a new organism, or at a crime