Difference between revisions of "Davidson Missouri W/Solving the HPP in vivo"
m (Solving the HPP in vivo moved to Davidson Missouri W/Solving the HPP in vivo) |
|||
| Line 1: | Line 1: | ||
| − | <center>[[Davidson | + | <center>[[Davidson Missouri W| <span style="color:red">Home</span>]] | [[Davidson Missouri W/Background Information| <span style="color:red">Background Information</span>]] | [[Davidson Missouri W/Solving the HPP in vivo| <span style="color:black">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] | [[Davidson Missouri W/Probability and Statistics| <span style="color:red">Probability and Statistics</span>]] | [[Davidson Missouri W/Gene splitting| <span style="color:red"> Gene Splitting </span>]] | [[Davidson Missouri W/Controlling Expression| <span style="color:red"> Controlling Expression </span>]] | [[Davidson Missouri W/Traveling Salesperson Problem| <span style="color:red">Traveling Salesperson Problem</span> ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| <span style="color:red">Backwards Promotion and Read-Through Transcription</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center> |
<hr> | <hr> | ||
Revision as of 19:40, 11 July 2007
Using the same flipping mechanism, we are trying to develop a bacterial computer which solves a new type of mathematical problem, the Hamiltonian Path problem
Contents
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.
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. If our reporter gene tolerates a HixC insertion then we can use it as a node on our graph.
The Traveling Salesman Problem
Although our current project is to develop a bacterial computer that solves Hamiltonian path problems, in the future we would like to tackle the Traveling Salesman problem using similar methods.
What is it?
Given a directed graph where each edge has a cost associated with it, what is the cheapest, or shortest, path to take such that you end at your starting point and visit every node exactly once?
How We Solve it
The addition of spacers in between nodes allows us to tackle this problem with the same flipping mechanism that we employ in our Hamiltonian path computer. Please visit this page for more information.
