Bacterial
Computing

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 DOI: 10.1145/1836543.1836550

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
bacterium will
replicate itself
approximately
every 30 minutes.
Growing a bacterium
overnight results
in approximately
a billion identical,
independent
biological-
processors.”