Undergraduate students find that a
genetically engineered machine can
solve Hamiltonian Path Problems.
By Jeffrey L. Poet, A. Malcolm Campbell,
Todd T. Eckdahl, and Laurie J. Heyer
Amultidisciplinary group of students from Missouri Western State University and Davidson College (under our mentorship) recently designed and constructed a proof-of-concept experiment to solve a Hamiltonian
Path Problem inside live bacteria. The students worked
within a new field called synthetic biology, which seeks to
apply engineering principles (including standardization,
modularity, and abstraction), mathematical modeling, and
molecular biology techniques to build biological machines
to perform functions with applications in medicine, the
environment, energy, and technology.
A Hamiltonian path is a sequence
of directed edges, in a directed graph,
that start at one node and end at another node while visiting all nodes
exactly once. A directed graph is a set
of nodes with directed edges between
some pairs of nodes. A Hamiltonian
Path Problem (HPP) asks, for a given
directed graph and specified beginning and ending nodes, does there exist a Hamiltonian path in the graph?
For example, the graph in Figure 1 has
a unique Hamiltonian path beginning
at node 1 and ending at node 5.
In 1994, Leonard Adleman (who put
the A in RSA cryptography) published a
seminal paper on DNA computing. The
article [ 1] described Adleman’s in vitro
experiment in which the edges of the
graph of Figure 1 were represented by
strands of DNA with the property that
each strand could only attach itself to
certain other strands.
DNA is composed of four nucleotides, represented by A, T, G, and C.
In double-stranded DNA, an A on one
strand always pairs with a T on the
other strand, and similarly, a G on one
strand always pairs with a C on the other. These A-T and G-C interactions are
called Watson-Crick base pairing.
Adleman constructed single-stranded segments of DNA so that as these
segments of DNA “found each other”
in the test tube, compatible segments
assembled by base pairing to form longer and longer pieces of double-stranded DNA. At the end of the binding step,
“A single E. coli
every 30 minutes.
Growing a bacterium
a billion identical,