Davidson Missouri W/Project Description
From 2007.igem.org
Wideloache (Talk | contribs) |
Macampbell (Talk | contribs) |
||
| Line 1: | Line 1: | ||
| - | 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. | + | The 2007 Davidson/Missouri Western (DMW) 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. | 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. | ||
Latest revision as of 21:12, 29 August 2007
The 2007 Davidson/Missouri Western (DMW) 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.
