Davidson Missouri W/Solving the HPP in vivo
From 2007.igem.org
Using the Hin/hixC flipping mechanism, we are developing a bacterial computer which solves a specific mathematical problem, the Hamiltonian Path problem.
The Hamiltonian Path Problem
A Hamiltonian Path is a trip through a graph which visits each node exactly once. A graph may have multiple Hamiltonian Paths, only one, or even none. Given a graph, a starting point and an endpoint, does it contain a Hamiltonian path?
We solve our problem by transforming E. coli cells with specially engineered plasmids.
Designing a Plasmid
Our plasmid consists of reporter genes and hixC sites. hixC sites are placed within the coding regions of our reporter genes. The reporter genes are joined in such a way as to represent a graph. Each reporter gene represents a node, and the connection of two reporter genes together without any hixC sites in between represents an edge.
Such a plasmid design allows us to flip the edges of the graph into all possible permutations. Each permutation represents a potential path through the graph; permutations with all the proper phenotypes can be selected for. This system therefore allows for the detection of computation, as solutions to the Hamiltonian Path problem will manifest themselves via the reporter genes.
Developing Nodes
We represent the graph's nodes with reporter genes. In order to allow for flipping, we must insert hixC sites within the coding regions of our reporter genes. We call this process gene splitting. The central issue with gene splitting is that an additional 13 amino acids are added within the resulting protein. If our reporter gene tolerates a hixC insertion, and still functions as a reporter properly, then we can use it as a node on our graph.
