Transcript PPT poster - Davidson College

Living Hardware to Solve the Hamiltonian Path Problem
Davidson College: Oyinade Adefuye, Will DeLoache, Jim Dickson, Andrew Martens, Amber Shoecraft, Mike Waters,
Dr. A. Malcolm Campbell, Dr. Karmella Haynes, Dr. Laurie Heyer
Missouri Western State University: Jordan Baumgardner, Tom Crowley, Lane Heard, Nick Morton, Michelle Ritter, Jessica Treece,
Matthew Unzicker, Amanda Valencia, Dr. Todd Eckdahl, Dr. Jeff Poet
Modeling a Bacterial Computer
Silicon computers are powerful tools for solving mathematical
problems but are inefficient parallel processors. For iGEM2007,
Davidson College and Missouri Western State University have
jointly developed a bacterial system capable of solving a
Hamiltonian Path Problem in vivo. Our system takes advantage
of E. coli’s exponential growth to address the complexity of this
problem in a way that traditional computers cannot. We
successfully detected solutions to a Hamiltonian Path Problem
through phenotypic screening.
To determine the feasibility of our system, we implemented
mathematical models to answer to following questions:
Does starting orientation matter?
No, after a large number of flips,
all orientations converge to the
same probability.
Can we detect a solution?
The Hamiltonian Problem (HPP) asks:
given a directed graph with designated
starting and ending nodes, is it possible
to travel through the graph visiting
every node exactly once?
Bacteria Successfully Solve the Problem!
The HPP constructs were transformed into E. coli expressing T7
RNA polymerase, and their phenotypes were observed. After
about two days, they had visible color. “Unflipped” colonies
exhibited uniform fluorescent phenotypes, while colonies
exposed to Hin protein varied in their fluorescence. Fluorescent
phenotypes were observed by eye and confirmed by fluorometer.
4 Nodes & 3
Edges
Yes, for a 14-edge graph with 7
nodes, growing 1 billion bacterial
computers gives a 99.9% chance of
detecting a solution. We
determined this using a cumulative
Poisson distribution. 1 mL of
culture contains 1 billion bacteria.
The Hamiltonian Path Problem
Number of Flips

e 
1 
x!
x0
k1
x
Cumulative Poisson Distribution
Are there too many false positives?
No, using MATLAB, we computed the ratio of true positive to

total positives and found that even for a 14-edge graph, the
ratio was above 0.05. Combined with PCR screening, this ratio
is well within detectable limits.
Possible Paths
through the graph
Extra Edge
False Positive
PCR Fragment Length
# of Edges in Graph
True Positive
# of Processors
Linear increases in graph complexity
yield exponential increases in the
number of possible paths through a
graph. Due to the absence of an
efficient algorithm, parallel processing
is required when attempting to solve
complex graphs in a limited amount of
time. The exponential growth of E. coli
computers provides the required
processing power.
Probability of HPP Solution
Abstract
PCR Fragment Length
Building a Bacterial Computer
Cell Division
For our system to work, reporter
genes must maintain
functionality despite the addition
of 13 amino acids. We were able
to perform successful
hixC insertions in both GFP and RFP. We therefore designed the
following HPP constructs to test our system on 2 simple graphs:
Design Principles
As a part of iGEM2006, we reconstituted a
hin/hix DNA recombination mechanism as
standard biobricks for use in E. coli. This
system allows for rearrangement of DNA
segments that are flanked by hixC sites and
was implemented in our HPP computer in the
following way:
1
4
3
2
5
• Represent each node as a reporter gene
• Represent each edge as a flippable unit of DNA flanked by hixC sites
Flipping was also detected by
PCR, using multiplex primers
that bound to three distinct
regions of the HPP-A
constructs. Different edge
orientations produce 8 unique
PCR product lengths.
MW
ABC
ACB
BAC
Hin
ABC
Hin
ACB
Hin
BAC
Both methods show strong
evidence for flipping of
DNA, and PCR shows that
some of the bacteria may
have solved the problem.
Acknowledgements
• Flipping generates a random walk through the graph
• A solution is screened for by phenotype
Hin-mediated Recombination
Edge
hixC sites
We thank The Duke Endowment, HHMI, NSF, Genome Consortium
for Active Teaching, James G. Martin Genomics Program, MWSU
Student Government Association, MWSU Student Excellence Fund,
MWSU Foundation, and the MWSU Summer Research Institute.
Team members Oyinade Adifuye and Amber Shoecraft are from
North Carolina Central University and Johnson C. Smith University,
respectively. Special thanks to the iGEM organizers and
community. We had a great time!