BIOLOGICAL INSPIRATION FOR COMPUTING 283
clease and ligase, while the software and input were encoded by double-stranded DNA. Programming
was implemented by choosing appropriate software molecules. The automaton processed the input
molecule through a cascade of restriction, hybridization, and ligation cycles, producing a detectable
output molecule encoding the automaton’s computational result. However, a finite-state automaton is
not Turing-complete, and the actual demonstration of a Turing-complete biomolecular machine with a
set of primitives sufficient for universal computation has yet to be shown experimentally.^108
Since Adleman’s initial publication, researchers have explored many variants of the basic biological
approach. One such variant is the use of RNA, which simplifies the process of removing invalid se-
quences. In this variant, RNA is used for the solution sequences and DNA is used to represent an
element of an invalid solution. Thus, any potential solution that was invalid would be represented by a
DNA-RNA hybridized double strand. A single enzyme, ribonuclease H, destroys all DNA-RNA hy-
bridized pairs, leaving only valid solutions. This is significantly simpler than the use of many, poten-
tially noncompatible enzymes necessary to mark and destroy the appropriate DNA-DNA hybrids in the
traditional method. (In developing an algorithm based on RNA computing for solving a certain chess
problem, Cukras et al.^109 found that although the algorithm was able to recover many more correct
solutions than would be expected at random, the persistence of errors continued to present the most
significant challenge.)
Other variants of the process seek to automate or simplify the management of stages of the reac-
tions. In the original experiments, the DNA reactions took place in solution in test tubes or other
containers, with stages of the process controlled by humans—for example, by introducing new en-
zymes, changing the temperature (perhaps to break chemical bonds), or mixing DNA solutions. Some of
these steps can be automated through the use of laboratory robotics. In some variants, DNA strands are
chemically anchored to various types of beads; these beads can be designed with different properties,
such as being magnetic or electrically charged, allowing the manipulation of the DNA strands through
the application of electromagnetic fields. Another solution is to use microfluidic technologies, which
consist of MEMS devices that operate as valves and pumps; a properly designed system of pipettes and
microfluidic devices offers significant advantages by automating tasks and reducing the total volume of
materials required.^110
Still another variant is to restrict the chemical operations to a surface, rather than to a three-
dimensional volume.^111 In this approach, DNA sequences, perhaps representing all of the solution
space of an NP problem, would be chemically attached to a surface. Challenges in this approach include
the attachment chemistry, addressing particular strands on the surface, and determining whether chemi-
cal attachment interferes with DNA hybridization and enzymatic reactions.
A second class of biomolecular computing begins with an input and a program represented in a
molecular form and evolves the program in a number of steps to process the input to produce an output.
In this approach, the complexity of the problem does not manifest itself in the number of starting
molecules, but rather in the form of the rules provided and the amount of time or number of steps
needed to fully evaluate a particular problem and input. For example, in the programmed mutagenesis
method, DNA molecules that represent rewrite rules are combined with DNA molecules that encode
input data and program. When the combined mixture of these DNA molecules is thermally cycled in the
(^108) However, Rothemund has provided a highly detailed description of a Turing-complete DNA computer. See P.W.K.
Rothemund, “A DNA and Restriction Enzyme Implementation of Turing Machines,” pp. 75-119 in DNA Based Computers: Pro-
ceedings of a DIMACS Workshop, Vol. 27, R.J. Lipton and E.B. Baum eds., DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, American Mathematical Society, Princeton, NJ, 1996.
(^109) A.R. Cukras, D. Faulhammer, R.J. Lipton, and L.F. Landweber, “Chess Games: A Model for RNA Based Computation,”
Biosystems 52(1-3):35-45, 1999.
(^110) A. Gehani and J.H. Reif, “Micro-Flow Bio-Molecular Computation,” BioSystems 52(1-3):197-216, October 1999.
(^111) L.M. Smith, R.M. Corn, A.E. Condon, M.G. Lagally, A.G. Frutos, Q. Liu, and A.J. Thiel, “A Surface-based Approach to DNA
Computation,” Journal of Computational Biology 5(2):255-267, 1998.