Next Generation (OS *E.
coli* v2.0)

Hamiltonian Path Problem

Is there a Hamiltonian path through these 7 nodes using the directed edges?

You must start at 1, end at 5, and visit every node exactly once.

The only way to know is by trial and error.

What if bacteria could solve this problem for us?

We'd have to formulate the problem so bacteria could understand and solve the problem.

Is there a Hamiltonian path through these 7 genes using the available edges (half-gene assemblies)?

You must start at 1, end at 5, and visit every node exactly once.

Each ^ represents a Hix site.

5 is a transcriptional terminator.

The promoter is fused to the first half-gene.

Hin-mediated problem solving without human intervention.

Induce random flipping and select for bacteria that have solved the problem.

One liter of cells contains 10

^{12}bacteria, each with 300 copies of the DNA problem.Solution = 1, 4, 7, 2, 3, 6, 5.

We have our first bacterial HPP running this week!

© Copyright 2007 Department of Biology, Davidson College, Davidson, NC 28036

Send comments, questions, and suggestions to: