282 CATALYZING INQUIRY
Box 8.3
Adleman and DNA Computing
Adleman used the tools of molecular biology to solve an instance of the directed Hamiltonian path problem.
A small graph was encoded in molecules of DNA, and the “operations” of the computation were performed
with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computa-
tions at the molecular level.
The Hamiltonian path problem is based on finding a special path through an arbitrarily connected set of nodes
(i.e., an arbitrary directed graph). (The adjective “directed” means that the connections between nodes are
unidirectional, so that a path from A to B does not mean necessarily that another connection from B to A
exists.) This path (the Hamiltonian path) is special in the sense that beginning with a specified entering node
and ending with a specified exiting node, a continuous path exists that enters and exits every other node once
and only once. Hamiltonian paths do not necessarily exist for a given directed graph, and their existence may
depend on an appropriate specific choice of entering and exiting nodes.
All known algorithms for determining whether an arbitrary directed graph with designated vertices has a Hamil-
tonian path exhibit worst-case exponential complexity, which means that there are some directed graphs with a
small number of nodes for which this determination would take an impractical amount of computing time.
One method for determining if a Hamiltonian path exists is illustrated in the first column of the table below.
Step Algorithmic Step Biological Equivalent
0 Establish directed graph notation Encode each node and directed node-to-node path as
as problem representation. a specific DNA sequence.
1 Generate all possible paths Combine large amounts of these DNA sequences,
through the graph. and with a sufficiently large quantity, the probability
that all possible paths will be generated is essentially
unity. (In general, these various combinations will
be in length several multiples of a single sequence.)
2 Keep only those paths that begin Use polymerase chain reaction (PCR) that amplifies
with a specified starting and only those molecules encoding paths that begin and
ending node. end with the specified nodes.
3 If the graph has n nodes, Separate only those sequences from step 2 that have
then keep only those paths that enter the correct length (corresponding to the number of
exactly n nodes. nodes in the graph).
4 Keep only those paths that enter Separate the sequences from step 3 that have a
all of the nodes of the graph at subsequence corresponding to each and every node.
least once.
5 If any paths remain, say, “Yes, a Use PCR amplification on the output of step 4, what
Hamiltonian path exists”; remains after step 5 represents the solution to the
otherwise, say “No.” problem.
SOURCE: Adapted from L.M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science 266(5187):1021-
1024, 1994.
