Davidson Missouri W

From 2007.igem.org

(Difference between revisions)
(→'''Math Related Notes''')
(→Our Successful Project)
 
(144 intermediate revisions not shown)
Line 1: Line 1:
-
===Davidson & Missouri Western Team Logos, iGEM2006=== <br>
+
<center>[[Davidson Missouri W| <span style="color:black">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:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] | [[Davidson Missouri W/Mathematical Modeling| <span style="color:red">Mathematical Modeling</span>]] | [[Davidson Missouri W/Gene splitting| <span style="color:red">Gene Splitting</span>]] | [[Davidson Missouri W/Results| <span style="color:red">Results</span>]] |  [[Davidson Missouri W/Traveling Salesperson Problem| <span style="color:red">Traveling Salesperson Problem</span> ]] | [[Davidson Missouri W/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center>
-
[[Image:EHOP.gif|thumb|300px|center| ]]
+
 
-
<br>
+
<hr>
-
[[Image:Ihop.PNG|thumb|300px|center| ]]
+
<br>
<br>
 +
[[Image:dmw_logo2.png|center]]
-
----
+
[[Image:Computer.png|center]]
-
== '''Team Meeting Notes''' ==
+
-
Western Meeting Notes 051407 to Present
+
<center>
-
[https://2007.igem.org/Davidson_Missouri_W/WesternMeetingNotes]
+
=The Team=
 +
</center>
 +
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"
 +
|-
 +
! style="color: white; background-color: black;"| The Team
 +
! style="color: white; background-color: black;" | The Faculty
 +
! style="color: white; background-color: black;" | School Logos
 +
! style="color: white; background-color: black;" | Group Photo
 +
|-
-
== '''Math Related Notes''' ==
+
|style="color: black; background-color: red;" align="center"| '''Davidson'''
 +
<b>
 +
[[Davidson Missouri W/Oyinade Adefuye|<span style="color:black">Oyinade Adefuye</span>]]
 +
<br>
 +
[[Davidson Missouri W/Will DeLoache|<span style="color:black">Will DeLoache</span>]]
 +
<br>
 +
[[Davidson Missouri W/Jim Dickson|<span style="color:black">Jim Dickson</span>]]
 +
<br>
 +
[[Davidson Missouri W/Andrew Martens|<span style="color:black">Andrew Martens</span>]]
 +
<br>
 +
[[Davidson Missouri W/Amber Shoecraft|<span style="color:black">Amber Shoecraft</span>]]
 +
<br>
 +
[[Davidson Missouri W/Mike Waters|<span style="color:black">Mike Waters</span>]]
 +
</b>
-
Notes 051407 to Present
+
|style="color: black; background-color: red;" align="center"|
-
[https://2007.igem.org/Davidson_Missouri_W/MathMeetingNotes]
+
<b>
 +
[[Davidson Missouri W/A. Malcolm Campbell|<span style="color:black">A. Malcolm Campbell</span>]]
 +
<br>
 +
[[Davidson Missouri W/Karmella Haynes|<span style="color:black">Karmella Haynes</span>]]
 +
<br>
 +
[[Davidson Missouri W/Laurie Heyer|<span style="color:black">Laurie Heyer</span>]]
 +
</b>
-
[[Image:AdelmanGraph.JPG|thumb|300px|center| ]] 
+
|style="color: black; background-color: white;" align="center"|
-
<br>   
+
[[Image:DavidsonLogo.gif]]
-
+
-
The Adelman Graph with its seven vertices and fourteen arcs is too large to attack with our approach without first testing our procedures. To this end, Michelle and Jeff have been investigating induced subgraphs of the Adelman Graph. Ideally, we would like to partition the Adelman Graph into smaller graphs that could be constructed and tested individually, then linked together to form one large construct representing the Adelman Graph. It seems the most critical property of a good test graph is a unique Hamiltonian path. The smallest graph with a unique Hamiltonian path would be two vertices connected with a single edge. This is the one pancake problem worked on (and successfully achieved!) by the Davidson-Missouri Western team in 2006. The first non-trival (from a mathematical standpoint) graph would be a transitive directed graph on three vertices. The concept of transitivity is pervasive in many areas of mathematics. In the real numbers, the relation > is transitive. That is, if a>b and b>c, then we know that a>c. One example of a transitive induced graph of the Adelman graph is the subgraph on the vertices 1, 4, and 2. Notice that the edges of the Adelman Graph between these three vertices are precisely 14, 42, and 12. This construct, and others like it, have a unique Hamiltonian path AND have the property that there are no false positive results. This may provide a setting in which to test some of our proposed procedures. 
+
-
   
+
-
Moving up a level, the graph below is nearly an induced subgraph of the Adelman Graph. (To be induced, it would require the arc 27 also be included, but to include this edge would destroy the property of having a unique Hamiltonian path.) This graph on four vertices with six edges provides a small example in which we can test our ability to biologically distinguish between true positives and false positives. There are 48 true positives for this graph (14, 47, 72 followed by the other three arcs in any order and any orientation). There are 42 false positives (14, 47, 74 followed by the other three arcs in any order but with at least one in forward orientation).     
+
-
[[Image:HamiltonInduced4.JPG|thumb|300px|center| ]] 
+
-
<br> 
+
-
 
+
-
The graph below is an induced subgraph of the Adelman Graph on five vertices with nine arcs. This graph has a unique Hamiltonian path AND contains the graph above. This might serve as a good intermediate on our way to the complete construction. Note also that this graph contains three transitive subgraphs (7,4,2), (4,7,2) and (1,4,2). Before jumping into constructions, we should carefully consider which coding sequence will correspond to each vertex of the Adelman Graph. If we are clever, it may be possible to piece together several smaller test constructs to efficiently create the full graph. Note: The counting of true positives and false positives for the graph below is non-trivial and in progress. 
+
-
 
+
-
[[Image:HamiltonInduced5.JPG|thumb|300px|center| ]]  
+
-
<br> 
+
-
   
+
-
=='''Proposed Construct with Cre/loxP'''==
+
-
== '''Students''' ==
+
|style="color: black; background-color: white;" align="center"|
 +
[[Image:Team1.jpg|thumb|center|300px]]
-
[[Image:Logo.gif]]
+
|-
-
• Will DeLoache, Junior Biology Major,  [mailto:wideloache@davidson.edu]
+
|style="color: black; background-color: gold;" align="center"|'''Missouri Western'''
 +
<b>
 +
[[Davidson Missouri W/Jordan Baumgardner|<span style="color:black;">Jordan Baumgardner</span>]]
 +
<br>
 +
[[Davidson Missouri W/Tom Crowley|<span style="color:black;">Tom Crowley</span>]]
 +
<br>
 +
[[Davidson Missouri W/Lane H. Heard|<span style="color:black;">Lane H. Heard</span>]]
 +
<br>
 +
[[Davidson Missouri W/Nickolaus Morton|<span style="color:black;">Nickolaus Morton</span>]]
 +
<br>
 +
[[Davidson Missouri W/Michelle Ritter|<span style="color:black;">Michelle Ritter</span>]]
 +
<br>
 +
[[Davidson Missouri W/Jessica Treece|<span style="color:black;">Jessica Treece</span>]]
 +
<br>
 +
[[Davidson Missouri W/Matthew Unzicker|<span style="color:black;">Matthew Unzicker</span>]]
 +
<br>
 +
[[Davidson Missouri W/Amanda Valencia|<span style="color:black;">Amanda Valencia</span>]]
 +
</b>
-
• Oyinade Adefuye, Senior Biology Major,  [mailto:oyinadeadefuye@yahoo.com]
+
|style="color: black; background-color: gold;" align="center"|
 +
<b>
 +
[[Davidson Missouri W/Todd Eckdahl|<span style="color:black;">Todd Eckdahl</span>]]
 +
<br>
 +
[[Davidson Missouri W/Jeff Poet|<span style="color:black;">Jeff Poet</span>]]
 +
</b>
-
• Jim Dickson, Junior Math and Economics Major,    [mailto:jidickson@davidson.edu]
+
|style="color: black; background-color: white;" align="center"|[[Image:MWLogo.gif]]
-
• Amber Shoecraft, Math Major,  [mailto:ashoecraft@jcsu.edu]
+
|style="color: black; background-color: white;" align="center"|[[Image:MWSUteam.jpeg|thumb|center|300px]]
 +
|-
-
• Andrew Martens, Senior Biology Major,  [mailto:anmartens@davidson.edu]
+
|}
 +
<br>
 +
<center>
-
• Michael Waters, Sophomore Biology Major,  [mailto:miwaters@davidson.edu]
+
=Our Successful Project=
 +
</center>
-
-----
+
{| border="1" cellpadding="5" cellspacing="0" align="center" width="90%"
 +
|-
 +
! style="color: black; background-color: red;" width="20%"| <font size="+1">In Depth</font>
 +
! colspan="3" style="color: black; background-color: red;" width="60%"| <font size="+1">Overview</font>
 +
|-
 +
|style="color: black; background-color: black;" align="center"|
 +
[[Davidson Missouri W/Background Information|<span style="color:red">Background Information</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Solving the HPP in vivo|<span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Mathematical Modeling|<span style="color:red">Mathematical Modeling</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Gene splitting|<span style="color:red">Gene Splitting</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Results|<span style="color:red">Results</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Traveling Salesperson Problem|<span style="color:red">Traveling Salesperson Problem</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Software|<span style="color:red">Software</span>]]
 +
<br><br><br>
 +
[[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]
 +
<br><br><Br>
 +
|Hamiltonian Path Problem
 +
As a part of iGEM2006, a combined team from Davidson College and Missouri Western State University reconstituted a hin/''hix'' DNA recombination mechanism which exists in nature in ''Salmonella'' as standard biobricks for use in ''E. coli''. The purpose of the 2006 combined team was to provide a proof of concept for a bacterial computer in using this mechanism to solve a variation of The Pancake Problem from Computer Science. This task utilized both biology and mathematics students and faculty from the two institutions.
-
[[Image:Header_01.gif]]
+
For 2007, we successfully continued our collaboration and our efforts to manipulate ''E. coli'' into mathematics problem solvers as we refine our efforts with the hin/''hix'' mechanism to explore another mathematics problem, the Hamiltonian Path Problem. This problem was the subject of a groundbreaking paper by Adleman in 1994 (see [[Davidson_Missouri_W/Resources_and_Citations | citations]]) where a unique Hamiltonian path was found ''in vitro'' for a particular directed graph on seven nodes. We were able to use bacterial computers to solve the Hamiltonian path problem ''in vivo''. ([[Davidson Missouri W/Background Information#Why Use Bacteria?|Why use a bacterial computer?]])
 +
<br>
 +
 
 +
[[Image:Adelman.png|thumb|300px|center|The Adleman graph.]] 
-
• Jordan Baumgardner, Junior Biology, Biochemistry/Molecular Biology Major,  [mailto:jbaumgardner@missouriwestern.edu]
+
<center> For the graph used in Adleman's paper (shown above), the Hamiltonian Path Problem would ask: can you find a path along the directed edges that travels from node 1 (green) to node 5 (red) and visits each node on the graph exactly once? <br>
 +
[https://static.igem.org/mediawiki/2007/6/6f/Adelmansolution.png Click here] for the solution.
 +
</center>
 +
|}
-
• Ryan Chilcoat, Junior Biology Major (Health Sciences),  [mailto:rchilcoat@missouriwestern.edu]
+
<br>
 +
<center> '''A Human Representation of the Adleman Graph. (mouse over to see the full effect)'''
-
• Tom Crowley, Senior Biochemisty/Molecular Biology Major,  [mailto:stc8033@missouriwestern.edu]
+
<html>
 +
<head>
 +
<link rel="stylesheet" href="https://2007.igem.org/wiki/index.php?title=User:Wideloache/igem2007.css&action=raw&ctype=text/css" type="text/css" />
 +
</style>
 +
</head>
 +
<body>
-
• Lane H. Heard, Central High School graduate,  [mailto:axenmoon@hotmail.com]
+
<div class="rollover">
 +
<center>
 +
<a href="#"></a>
 +
</center>
 +
</div>
 +
</body>
 +
</html>
-
• Nickolaus Morton, Junior Chemistry Major,  [mailto:nmorton@missouriwestern.edu]
+
<br>
 +
<br>
-
• Michelle Ritter, Junior Mathematics Major,  [mailto:mrr5418@missouriwestern.edu]
+
<br>
-
 
+
<hr>
-
• Jessica Treece, Junior Biology Major (Health Sciences),  [mailto:jtreece@missouriwestern.edu]
+
-
 
+
-
• Matthew Unzicker, Senior Biochemistry/Molecular Biology Major,  [mailto:mru8487@missouriwestern.edu]
+
-
 
+
-
• Amanda Valencia, Senior Biochem/Molecular Biology Major,  [mailto:avalencia@missouriwestern.edu]
+
-
 
+
-
== '''Faculty''' ==
+
-
[[Image:Logo.gif]]
+
-
 
+
-
• Malcolm Campbell [http://www.bio.davidson.edu/people/macampbell/macampbell.html], Professor, Department of Biology, [mailto:macampbell@davidson.edu]
+
-
 
+
-
• Karmella Haynes [http://www.bio.davidson.edu/people/kahaynes/kahaynes.html], Visiting Assistant Professor, Department of Biology, [mailto:kahaynes@davidson.edu]
+
-
 
+
-
• Laurie Heyer [http://www.davidson.edu/math/heyer/], Associate Professor, Department of Mathematics, [mailto:laheyer@davidson.edu]
+
-
 
+
-
Shipping Address: Malcolm Campbell, Biology Dept. Davidson College, 209 Ridge Road, Davidson, NC 28036 [(704) 894-2692]
+
-
 
+
-
-----
+
-
 
+
-
[[Image:Header_01.gif]]
+
-
 
+
-
• Todd Eckdahl [http://staff.missouriwestern.edu/~eckdahl/], Professor, Department of Biology, [mailto:eckdahl@missouriwestern.edu]
+
-
 
+
-
• Jeff Poet [http://staff.missouriwestern.edu/~poet/], Assistant Professor, Department of Computer Science, Mathematics, and Physics, [mailto:poet@missouriwestern.edu]
+
-
 
+
-
Shipping Address: Todd Eckdahl, Biology Department, Missouri Western State University, 4525 Downs Drive, Saint Joseph, MO, 64507 [(816) 271-5873]
+
-
 
+
-
== '''Project Overview'''==
+
-
 
+
-
<font color="blue">Hamiltonian Path Problem</font color>  
+
-
As a part of iGEM2006, a combined team from Davidson College and Missouri Western State University reconstituted a hin/hix DNA recombination mechanism which exists in nature in Salmonella as standard biobricks for use in E. coli.  The purpose of the 2006 combined team was to provide a proof of concept for a bacterial computer in using this mechanism to solve a variation of The Pancake Problem from Computer Science.  This task utilized both biology and mathematics students and faculty from the two institutions.
+
-
 
+
-
For 2007, we continue our collaboration and our efforts to manipulate E. coli into mathematics problem solvers as we refine our efforts with the hin/hix mechanism to explore another mathematics problem, the Hamiltonian Path Problem.  This problem was the subject of a groundbreaking paper by Adelman in 1994 (citation below) where a unique Hamiltonian path was found in vitro for a particular directed graph on seven nodes.  We propose to make progress toward solving the particular problem in vivo.
+
-
 
+
-
=='''Proposed Construct with Cre/loxP'''==
+
-
[[Image:HP_Graph1.jpg]]
+
-
 
+
-
In order to determine if a Hamiltonian Path exists in the directed graph above, we propose a plasmid design similar to that shown below:
+
-
 
+
-
 
+
-
[[Image:Plasmid before Excision.jpg]]
+
-
 
+
-
This cartoon represents a solved arangement of our proposed construct. Between the two pairs of BioBrick restriction enzyme sites lies a region containing eight flippable DNA fragments, each flanked by hixC sites (represented by the black, jagged rectangles). Each node of the graph represents one of the following genes: GFP (Green Fluorescent Protein), Kanamycin Resistance, cre, pir200, and a transcription terminator. Each edge of the graph is included in the construct between two hixC sites. In the presence of Hin protein, flipping of the edges at hixC sites will produce random walks through the graph. When flipped into the correct orientation and located upstream of any transcription terminators, a given gene will be transcribed (denoted by a bold outline in the cartoon above). In the solved arrangement shown above, a Hamiltonian Path is determined to exist in the graph because all genes are expressed, and no extra edges exist in the coding region. Extra edges in the coding region can be detected by gel electrophoresis.
+
-
 
+
-
The four reporter genes used in the construct above will produce three distinct phenotypes when in the solved orientation. GFP will cause the E. Coli cells to glow green, Kanamycin resistance will allow the cells to grow in the presence of the antibiotic, Kanamycin, and cre and pir200 will cause the entire DNA region between the two loxP sites to be excised into a separate plasmid and amplified. When the cre gene is in the solved orientation, it produces the Cre protein. It has been demonstrated that Cre can bind to two separated loxP sites and excise the DNA in the middle, forming a new plasmid [http://www.ncbi.nlm.nih.gov/sites/entrez?cmd=Retrieve&db=PubMed&list_uids=9526700&dopt=Abstract]. If Cre was produced, then the plasmid above would be cut at its loxP sites, and produce the two plasmids shown below.
+
-
 
+
-
[[Image:Excised Plasmid1.jpg]]
+
-
 
+
-
The DNA fragment located between the two loxP sites has now been excised and formed into a new plasmid. The E. Coli cell has essentially spit out the answer to the Hamiltonian Path Problem on a separate plasmid that can be easily isolated. This solved plasmid is resistant to kanamycin (due to the solved orientation of the kanamycin resistance gene) and contains the gamma-ori origin of replication. It has been shown that pi-protein (transcribed by the pir200 gene) initiates amplification of plasmids with the gamma-ori origin of replication [http://www.ncbi.nlm.nih.gov/sites/entrez?cmd=Retrieve&db=PubMed&list_uids=9526700&dopt=Abstract]. Therefore, only when the pir200 gene is in the solved orientation will the excised plasmid will be amplified.
+
-
 
+
-
[[Image:Orig Plasmid after excision.jpg]]
+
-
 
+
-
 
+
-
The original plasmid has now lost all of the DNA between the two loxP sites. The pBad promoter (upstream of the first loxP site) has been moved just upstream of the ribsosomal binding site and the cI gene (downstream of the second loxP site). This rearrangement will cause the transcription of cI, a gene that represses the Cro promoter -P(R)- in lamda phage by binding to the first and second operator regions (Ptashne, 2004).
+
-
 
+
-
By constructing a plasmid whose transcription of Hin is dependent on promotion from the  P(R) promoter, in the manner shown below, we can terminate the transcription of Hin (and the flipping of hixC sites) whenever a plasmid is excised from the original construct to produce cI transcription.
+
-
 
+
-
[[Image:Un-Repressed Hin Plasmid.jpg]]
+
-
 
+
-
The plasmid containing Hin will have resistance to a different antibiotic than the original construct plasmid or the excised plasmid (Chloramphenicol for instance) and would have a similar design to the cartoon above.
+
-
 
+
-
[[Image:Repressed Hin Plasmid.jpg]]
+
-
 
+
-
Once pBad is joined with the RBS and cI gene in the original plasmid, transcription of cI would occur, and transcription of Hin would be repressed. This would be a mechanism for stopping Hin-induced flipping once a solution had been found.
+
-
 
+
-
In order to build the proposed construct, a hixC site must be inserted into each reporter gene. Our lab has already successfully inserted hixC into GFP, retaining its functionality [http://www.bio.davidson.edu/Courses/Immunology/Students/spring2006/Acker/Acker_finalpaperGFP.doc]. We have also found literature on the successful splitting of the cre gene [http://www3.interscience.wiley.com/cgi-bin/abstract/104558885/ABSTRACT?CRETRY=1&SRETRY=0].
+
-
 
+
-
== '''Resources / Citations'''==
+
-
 
+
-
[https://2006.igem.org/wiki/index.php/The_What%27s_and_How%27s Davidson's Wet Lab Protocols]
+
-
 
+
-
[https://2006.igem.org/wiki/index.php/MWSU_protocols Missouri Western's Wet Lab Protocols]
+
-
 
+
-
[http://gcat.davidson.edu/iGEM07/genesplitter.html Spliting Genes Web Tool]
+
-
 
+
-
Cool site for Breakfast
+
-
[http://www.cut-the-knot.org/SimpleGames/Flipper.shtml]
+
-
 
+
-
Karen Acker's paper describing GFP and TetA(c) with Hix insertions
+
-
[http://www.bio.davidson.edu/Courses/Immunology/Students/spring2006/Acker/Acker_finalpaperGFP.doc]
+
-
 
+
-
Bruce Henschen's paper describing one-time flippable Hix sites
+
-
[http://www.bio.davidson.edu/Courses/genomics/2006/henschen/Bruce_Finalpaper.doc]
+
-
 
+
-
Intro to Hamiltonian Path Problem and DNA
+
-
[http://www.ams.org/featurecolumn/archive/dna-abc2.html]
+
-
 
+
-
Adelman, LM. Molecular Computation of Solutions To Combinatorial Problems. Science.  11 November 1994. Vol. 266. no. 5187, pp. 1021 - 1024
+
-
 
+
-
Ptashne, Mark.  A Genetic Switch: Phage Lambda Revisited, Third Edition. New York. Cold Spring Harbor Laboratory Press: 2004.
+
-
 
+
-
== '''Literature and Registry Research'''==
+
-
 
+
-
'''Registry Search for Possible Promoters:'''
+
-
   
+
-
BBa_J24669 --- arabinose induced
+
-
 
+
-
BBa_R0082 --- Is upstream of the ompC porin gene
+
-
 
+
-
BBa_R0074 --- Penl regulated
+
-
 
+
-
BBa_I14017 --- P(Rhl)
+
-
 
+
-
BBa_I14018 --- P (Bla) --> amp resistance
+
-
 
+
-
BBa_J3902 --- Pr Fe (Pl + Pll rus operon)
+
-
 
+
-
BBa_R0077 --- CinR --> thought to have own terminator
+
-
 
+
-
BBa_R0078 --- CinR (no RBS)
+
-
 
+
-
BBa_R0062 --- luxR & HSL regulated -- luxpR
+
-
 
+
-
Possibly the use of Constitutive Promoter Family Members to strengthen other promoters.
+
-
 
+
-
'''Literature Search for Polycistronic Genes on Plasmids'''
+
-
 
+
-
Sol Operon
+
-
http://www.jstage.jst.go.jp/article/bbb/71/1/58/_pdf
+
-
 
+
-
Transfer (tra) Operon
+
-
http://www.pubmedcentral.nig.gov/picrender.fcgi?artid=1347297&blobtype=pdf
+
-
Oligopeptide Permease (opp)
+
<Previous Section | [[Davidson Missouri W/Background Information | Next Section>]]
-
http://www.pubmedcentral.nig.gov/picrender.fcgi?artid=1087318&blobtype=pdf
+
</center>

Latest revision as of 04:32, 27 October 2007

Home | Background Information | Current Project: Solving the Hamiltonian Path Problem in vivo | Mathematical Modeling | Gene Splitting | Results | Traveling Salesperson Problem | Software | Resources and Citations


Dmw logo2.png
Computer.png

The Team

The Team The Faculty School Logos Group Photo
Davidson

Oyinade Adefuye
Will DeLoache
Jim Dickson
Andrew Martens
Amber Shoecraft
Mike Waters

A. Malcolm Campbell
Karmella Haynes
Laurie Heyer

DavidsonLogo.gif

Team1.jpg
Missouri Western

Jordan Baumgardner
Tom Crowley
Lane H. Heard
Nickolaus Morton
Michelle Ritter
Jessica Treece
Matthew Unzicker
Amanda Valencia

Todd Eckdahl
Jeff Poet

MWLogo.gif
MWSUteam.jpeg


Our Successful Project

In Depth Overview

Background Information


Current Project: Solving the Hamiltonian Path Problem in vivo


Mathematical Modeling


Gene Splitting


Results


Traveling Salesperson Problem


Software


Resources and Citations


Hamiltonian Path Problem

As a part of iGEM2006, a combined team from Davidson College and Missouri Western State University reconstituted a hin/hix DNA recombination mechanism which exists in nature in Salmonella as standard biobricks for use in E. coli. The purpose of the 2006 combined team was to provide a proof of concept for a bacterial computer in using this mechanism to solve a variation of The Pancake Problem from Computer Science. This task utilized both biology and mathematics students and faculty from the two institutions.

For 2007, we successfully continued our collaboration and our efforts to manipulate E. coli into mathematics problem solvers as we refine our efforts with the hin/hix mechanism to explore another mathematics problem, the Hamiltonian Path Problem. This problem was the subject of a groundbreaking paper by Adleman in 1994 (see citations) where a unique Hamiltonian path was found in vitro for a particular directed graph on seven nodes. We were able to use bacterial computers to solve the Hamiltonian path problem in vivo. (Why use a bacterial computer?)


The Adleman graph.
For the graph used in Adleman's paper (shown above), the Hamiltonian Path Problem would ask: can you find a path along the directed edges that travels from node 1 (green) to node 5 (red) and visits each node on the graph exactly once?

Click here for the solution.


A Human Representation of the Adleman Graph. (mouse over to see the full effect)




<Previous Section | Next Section>

Retrieved from "http://2007.igem.org/wiki/index.php/Davidson_Missouri_W"