DNA NANOTECHNOLOGY AND ITS BIOLOGICAL APPLICATIONS - Bio-Inspired and Nanoscale Integrated Computing - page 354

Each of these DNA nanostructures was a linear DNA helix that corresponded to a
path in the graph. If the graph had a Hamiltonian path, then one of these DNA
nanostructures encoded the Hamiltonian path. Through conventional biochem-
ical extraction methods, Adelman was able to isolate only DNA nanostructures
encoding Hamiltonian paths and, by determining their sequence, the explicit
Hamiltonian path. It should be mentioned that this landmark experiment was
designed and demonstrated experimentally by Adleman alone, a computer
scientist with limited training in biochemistry.
13.3.2. The Nonscalability of Adelman's Experiment
While this experiment founded the field of DNA computing, it was not scalable in
practice, since the number of different DNA strands needed increased exponentially
with the number of nodes of the graph. Although there can be an enormous number
of DNA strands in a test tube (10 15 or more, depending on solution concentration),
the size of the largest graph that could be solved by his method was limited to at
most a few dozen nodes. This is not surprising, since finding the Hamiltonian path is
an NP complete problem, whose solution is likely to be intractable using conven-
tional computers. Even though DNA computers operate at the molecular scale, they
are still equivalent to conventional computers (e.g., deterministic Turing machines)
in computational power. This experiment taught a healthy lesson to the DNA
computing community (which is now well recognized): Carefully examine scalability
issues and judge any proposed experimental methodology by its scalability.
13.3.3. Autonomous Biomolecular Computation
Shortly following Adleman's experiment, there was a burst of further experiments
in DNA computing, many of which were quite ingenious. However, almost none
of these DNA computing methods were autonomous, and instead required many
tedious laboratory steps to execute. In retrospect, one of the most notable aspects
of Adleman's experiment was that the self-assembly phase of the experiment was
completely autonomous—it required no exterior mediation (the bulk of the labor
was in the nonautonomous molecular sorting steps). The strategy can be termed
generate-and-sort, since all possible answers are created and incorrect solutions
are subsequently discarded. Maximizing molecular autonomy makes an experi-
mental laboratory demonstration much more feasible as the scale increases. The
remaining sections mostly discuss autonomous devices for biomolecular computa-
tion based on self-assembly.
13.4. SELF-ASSEMBLED DNA TILES AND LAT TICES
13.4.1. Computation By Self-Assembly
The most fundamental way computer science ideas have impacted DNA nanos-
tructure design is via the pioneering work by theoretical computer scientists on a