From 2007.igem.org

---

Revision as of 19:50, 2 August 2007

The 2007 Davidson/Missouri Western iGEM team is building an E. coli computer capable of solving the Hamiltonian Path Problem. E. coli provide the massive parallel processing power required to solve this computationally intense problem from Graph Theory. We use a Hin/hixC DNA recombination mechanism to randomly generate possible paths through the graph. We then use gene expression and fragment length to screen for a Hamiltonian Path.

To construct our computer, we have inserted hixC sites into reporter genes in a location that destroys the gene’s function when the split segments are not united but allows for normal gene expression when the two segments are contiguous. So far we have successfully split GFP and RFP in this manner. Our method demands that the Hin/hixC system be able to rearrange multiple DNA elements into every possible ordering. Therefore, we have tested and confirmed that Hin/hixC can rearrange 2 DNA elements into all 8 signed permutations. Our math modeling shows that it will be feasible to detect true Hamiltonian Paths even in complex graphs. We are close to testing our first construct on a simple 3-node graph.