http://2007.igem.org/wiki/index.php?title=Special:Contributions&feed=atom&limit=50&target=Miwaters&year=&month=2007.igem.org - User contributions [en]2024-03-28T11:42:16ZFrom 2007.igem.orgMediaWiki 1.16.5http://2007.igem.org/wiki/index.php/File:MWSU_iGEM06.JPGFile:MWSU iGEM06.JPG2007-09-26T21:18:31Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:MWSU_Todd_fish.JPGFile:MWSU Todd fish.JPG2007-09-26T21:18:16Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Lableaner.jpgFile:Lableaner.jpg2007-09-26T21:16:51Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Example123.jpgFile:Example123.jpg2007-09-26T21:16:30Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/A._Malcolm_CampbellDavidson Missouri W/A. Malcolm Campbell2007-09-26T21:16:16Z<p>Miwaters: </p>
<hr />
<div>A. Malcolm Campbell<br />
[[Image:Example123.jpg|thumb|300px|center|]]<br />
<br />
I am a professor of biology at Davidson College. <br />
<br />
[[Image:GCATshirtFront.jpg|thumb|300px|center|]]<br />
I am the founding director of [http://www.bio.davidson.edu/projects/GCAT/gcat.html '''GCAT'''] (Genome Consortium for Active Teaching) and the [http://www.bio.davidson.edu/programs/Genomics/genomics_overview.html James G. Martin Genomics Program]. <br />
<br />
We have participated in iGEM for three years: [https://2006.igem.org/wiki/index.php/Davidson_2005 2005], [http://parts2.mit.edu/wiki/index.php/Davidson_2006 2006], and now [https://2007.igem.org/Davidson_Missouri_W 2007]. <br />
<center><br />
'''2005'''<br />
[[Image:synthases.jpg|thumb|300px|center|]]<br />
<br />
'''2006'''<br />
[[Image:EHOP.gif|thumb|300px|center|]]<br />
<br />
'''2007'''<br />
[[Image:DMW.jpg|thumb|300px|center|]]<br />
<br />
A. Malcolm Campbell<br />
[[Image:lableaner.jpg|thumb|200px|center]]<br />
</center></div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/A._Malcolm_CampbellDavidson Missouri W/A. Malcolm Campbell2007-09-26T21:16:01Z<p>Miwaters: </p>
<hr />
<div>A. Malcolm Campbell<br />
[[Image:Example1.jpg|thumb|300px|center|]]<br />
<br />
I am a professor of biology at Davidson College. <br />
<br />
[[Image:GCATshirtFront.jpg|thumb|300px|center|]]<br />
I am the founding director of [http://www.bio.davidson.edu/projects/GCAT/gcat.html '''GCAT'''] (Genome Consortium for Active Teaching) and the [http://www.bio.davidson.edu/programs/Genomics/genomics_overview.html James G. Martin Genomics Program]. <br />
<br />
We have participated in iGEM for three years: [https://2006.igem.org/wiki/index.php/Davidson_2005 2005], [http://parts2.mit.edu/wiki/index.php/Davidson_2006 2006], and now [https://2007.igem.org/Davidson_Missouri_W 2007]. <br />
<center><br />
'''2005'''<br />
[[Image:synthases.jpg|thumb|300px|center|]]<br />
<br />
'''2006'''<br />
[[Image:EHOP.gif|thumb|300px|center|]]<br />
<br />
'''2007'''<br />
[[Image:DMW.jpg|thumb|300px|center|]]<br />
<br />
A. Malcolm Campbell<br />
[[Image:lableaner.jpg|thumb|200px|center]]<br />
</center></div>Miwatershttp://2007.igem.org/wiki/index.php/File:GCATshirtFront.jpgFile:GCATshirtFront.jpg2007-09-26T21:14:48Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/A._Malcolm_CampbellDavidson Missouri W/A. Malcolm Campbell2007-09-26T21:14:18Z<p>Miwaters: </p>
<hr />
<div>A. Malcolm Campbell<br />
[[Image:Example.jpg|thumb|300px|center|]]<br />
<br />
I am a professor of biology at Davidson College. <br />
<br />
[[Image:GCATshirtFront.jpg|thumb|300px|center|]]<br />
I am the founding director of [http://www.bio.davidson.edu/projects/GCAT/gcat.html '''GCAT'''] (Genome Consortium for Active Teaching) and the [http://www.bio.davidson.edu/programs/Genomics/genomics_overview.html James G. Martin Genomics Program]. <br />
<br />
We have participated in iGEM for three years: [https://2006.igem.org/wiki/index.php/Davidson_2005 2005], [http://parts2.mit.edu/wiki/index.php/Davidson_2006 2006], and now [https://2007.igem.org/Davidson_Missouri_W 2007]. <br />
<center><br />
'''2005'''<br />
[[Image:synthases.jpg|thumb|300px|center|]]<br />
<br />
'''2006'''<br />
[[Image:EHOP.gif|thumb|300px|center|]]<br />
<br />
'''2007'''<br />
[[Image:DMW.jpg|thumb|300px|center|]]<br />
<br />
A. Malcolm Campbell<br />
[[Image:lableaner.jpg|thumb|200px|center]]<br />
</center></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Mike1.jpgFile:Mike1.jpg2007-09-26T21:13:14Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Amber2.jpgFile:Amber2.jpg2007-09-26T21:12:39Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Andrew2.jpgFile:Andrew2.jpg2007-09-26T21:12:09Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Jim1.jpgFile:Jim1.jpg2007-09-26T21:11:38Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/File:Will1.jpgFile:Will1.jpg2007-09-26T21:11:09Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Will_DeLoacheDavidson Missouri W/Will DeLoache2007-09-26T21:10:56Z<p>Miwaters: </p>
<hr />
<div><br />
<br />
[[Image:Will1.jpg]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Will_DeLoacheDavidson Missouri W/Will DeLoache2007-09-26T21:10:48Z<p>Miwaters: </p>
<hr />
<div> Will DeLoache <br />
<br />
[[Image:Will1.jpg]]</div>Miwatershttp://2007.igem.org/wiki/index.php/File:Oyinade1.jpgFile:Oyinade1.jpg2007-09-26T21:10:12Z<p>Miwaters: </p>
<hr />
<div></div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Jeff_PoetDavidson Missouri W/Jeff Poet2007-09-26T21:09:50Z<p>Miwaters: </p>
<hr />
<div>Jeff Poet</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Todd_EckdahlDavidson Missouri W/Todd Eckdahl2007-09-26T21:09:28Z<p>Miwaters: </p>
<hr />
<div>Todd Eckdahl<br />
<br />
As Professor and Chair of Biology at [http://www.missouriwestern.edu/ Missouri Western State University] in Saint Joseph, Missouri, I have many opportunities to work with undergraduate students. MWSU is a regional state liberal arts university with about 5000 students in attendance. Students in the [http://www.missouriwestern.edu/Biology/Biology Department] engage in a variety of independent research activities, including Synthetic Biology in 2006 and 2007.<br />
<br />
[[Image:MWSU_Todd_fish.JPG|thumb|300px|center|]]<br />
<br />
The Missouri Western iGEM team collaborated in 2006 with the team from Davidson College and we have joined them again in 2007. Our 2006 iGEM experience captivated the attention of our University and our community. In 2007 and beyond, we hope to build upon that excitement.<br />
<br />
[[Image:MWSU_iGEM06.JPG|thumb|300px|center|rotate|]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Laurie_HeyerDavidson Missouri W/Laurie Heyer2007-09-26T21:08:53Z<p>Miwaters: </p>
<hr />
<div>Laurie Heyer</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Karmella_HaynesDavidson Missouri W/Karmella Haynes2007-09-26T21:08:38Z<p>Miwaters: </p>
<hr />
<div>Karmella Haynes</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Amanda_ValenciaDavidson Missouri W/Amanda Valencia2007-09-26T21:06:11Z<p>Miwaters: </p>
<hr />
<div>Amanda Valencia</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Matthew_UnzickerDavidson Missouri W/Matthew Unzicker2007-09-26T21:05:47Z<p>Miwaters: </p>
<hr />
<div>Matthew Unzicker</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Jessica_TreeceDavidson Missouri W/Jessica Treece2007-09-26T21:04:13Z<p>Miwaters: </p>
<hr />
<div>Jessica Treece <br />
<br />
I am junior Biology W/Health Science Emphasis Major at Missouri Western. Next fall I will be attending Kansas City University of Medicine and Biosciences for medical school. Currently I am a student ambassador for the University and and RA in our all freshman residence hall. When time sneaks into my schedule, I enjoy hanging out with my friends and beating them in bowling every Wednesday night!</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Jessica_TreeceDavidson Missouri W/Jessica Treece2007-09-26T21:03:59Z<p>Miwaters: </p>
<hr />
<div>Jessica Treece <br />
<br />
I am junior Biology W/Health Science Emphasis Major at Missouri Western. Next fall I will be attending Kansas City University of Medicine and Biosciences for medical school. Currently I am a student ambassador for the University and and RA in our all freshman residence hall. When time sneaks into my schedule, I enjoy hanging out with my friends and beating them in bowling every Wednesday night! <br />
<br />
Retrieved from "http://gcat.davidson.edu/GcatWiki/index.php/Davidson_Missouri_W/Jessica_Treece"</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Michelle_RitterDavidson Missouri W/Michelle Ritter2007-09-26T21:03:42Z<p>Miwaters: </p>
<hr />
<div>Michelle Ritter</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Nickolaus_MortonDavidson Missouri W/Nickolaus Morton2007-09-26T21:03:21Z<p>Miwaters: </p>
<hr />
<div>Nickolaus Morton</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Lane_H._HeardDavidson Missouri W/Lane H. Heard2007-09-26T21:03:00Z<p>Miwaters: </p>
<hr />
<div>Lane H. Heard</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Tom_CrowleyDavidson Missouri W/Tom Crowley2007-09-26T21:02:26Z<p>Miwaters: </p>
<hr />
<div>Tom Crowley</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Jordan_BaumgardnerDavidson Missouri W/Jordan Baumgardner2007-09-26T21:01:58Z<p>Miwaters: </p>
<hr />
<div>I am a junior Biochemistry and Molecular Biology Major here at Missouri Western. My intention after graduation from this institution is to go to medical school. Not only do I participate with research and all of my classes, but I also work in the Admissions Office and I am an RA in an all Freshman Hall. When I find free time, I enjoy watching movies, listening to all types of music, and playing video games.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Mike_WatersDavidson Missouri W/Mike Waters2007-09-26T21:01:29Z<p>Miwaters: </p>
<hr />
<div>I am a sophomore biology major at Davidson from Centreville, Virginia. I'm interested in synthetic biology and genomics as well as organic chemistry, Spanish, and Davidson's humanities program. I hope to study synthetic control of gene expression and expression "abnormality" in the future. I'm the director of medical donations for Davidson's Timmy Foundation and I wrestle at 197 lbs. for the 'cats. <br />
<br />
<br> <br />
<br />
[[Image:Mike1.jpg|center|250px|]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Amber_ShoecraftDavidson Missouri W/Amber Shoecraft2007-09-26T21:00:44Z<p>Miwaters: </p>
<hr />
<div>I graduated in Spring of 2007 from Johnson C. Smith University in Charlotte,NC, with a Bachlors of Science with a concentration in Mathematics. In fall of 2007, I will start graduate school at the Ohio State University in Columbus,Ohio where I will major in Statistics. My goal is to get a PhD in Statistics and then become a professor or be a statistician for a company.<br />
<br />
[[Image:Amber2.jpg]]Amber Shoecraft</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Andrew_MartensDavidson Missouri W/Andrew Martens2007-09-26T21:00:14Z<p>Miwaters: </p>
<hr />
<div>I am a senior undergraduate biology major at Davidson College. I am a biology major, but I also have strong interests in computer science and Japanese. I come from Chicago, but I grew up in France; my parents currently live in Moscow.<br />
<br />
私はデービドソン大学の四年生です。専門は生物学ですけどコンピューターサイエンスと日本語にも興味があります。<br />
シカゴから来ましたけど子供の時にフランスに住んでいました。今両親はモスクワに住んでいます。<br />
<br />
[[Image:Andrew2.jpg]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Jim_DicksonDavidson Missouri W/Jim Dickson2007-09-26T20:59:40Z<p>Miwaters: </p>
<hr />
<div>[[Image:Jim1.jpg]]<br />
<br />
Jim Dickson<br />
<br />
Mathematics and Economics double major. <br />
<br />
Davidson Class of 2009 <br />
<br />
email: jidickson@davidson.edu<br />
<br />
I'm doing math modeling for the Davidson / Missouri Western 2007 IGEM team. I do a lot of programming in Matlab. I've been looking at problems in the areas of probability and graph theory. The team as a whole is trying to use tools from Genomics to solve the Hamiltonian Path Problem and the Traveling Salesperson Problem. Please contact me if you have any questions regarding my work or math modeling / Matlab in general. <br />
<br />
I'm interested in graduate school programs in Applied Math and other math / problem solving intensive areas. In my spare time I enjoy playing chess, sports and other games. I'm actually a relatively strong chess player with a USCF rating of 2035 I'm one of the top 2500 players in the country and one of the top 200 juniors. As a Bonner Scholar I'm also very active in community service related activities.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Will_DeLoacheDavidson Missouri W/Will DeLoache2007-09-26T20:58:56Z<p>Miwaters: </p>
<hr />
<div> Will DeLoache <br />
<br />
Retrieved from "http://gcat.davidson.edu/GcatWiki/index.php/Davidson_Missouri_W/Will_DeLoache"</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Oyinade_AdefuyeDavidson Missouri W/Oyinade Adefuye2007-09-26T20:58:29Z<p>Miwaters: </p>
<hr />
<div>[[Image:Oyinade1.jpg]]Oyinade Adefuye</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Resources_and_CitationsDavidson Missouri W/Resources and Citations2007-09-26T20:56:04Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
=Protocols, Tools and Guidelines=<br />
[[Davidson Missouri W/Davidson_Protocols| Davidson's Wet Lab Protocols]]<br />
<br />
[[Davidson_Missouri_W/MWSU_protocols| Missouri Western's Wet Lab Protocols]]<br />
<br />
[http://gcat.davidson.edu/iGEM07/genesplitter.html Spliting Genes Web Tool]<br />
<br />
[http://www.bio.davidson.edu/courses/Molbio/Protocols/ORIs.html '''Compatibility of Plasmids''']<br />
<br />
[http://tools.wikimedia.de/~tangotango/nubio/ A Site with an FAQ on Wikis]<br />
<br />
[http://spreadsheets.google.com/pub?key=pw-NamR_FPJOfhl6mDrkZcw Davidson Freezer Stocks - iGEM 2007 Project]<br />
<br />
[[Media:VT_Presentation.ppt| Davidson's PPT for VT]]<br />
#'''DMW Part Numbers for 2007 are BBa_I715000 to BBa_I715999.''' <br />
#[http://partsregistry.org/Help:BioBrick_Part_Names How to Name a New Part]<br />
#[http://partsregistry.org/Add_a_Part_to_the_Registry Entering the Part to the Registry]<br />
#[http://partsregistry.org/Help:Part_Features How to Annotate a Part]<br />
<br />
=References=<br />
#Cool site for Breakfast [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml]<br />
#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]<br />
#Bruce Henschen's paper describing one-time flippable Hix sites [http://www.bio.davidson.edu/Courses/genomics/2006/henschen/Bruce_Finalpaper.doc]<br />
#Intro to Hamiltonian Path Problem and DNA [http://www.ams.org/featurecolumn/archive/dna-abc2.html]<br />
#Adleman, LM. Molecular Computation of Solutions To Combinatorial Problems. Science. 11 November 1994. Vol. 266. no. 5187, pp. 1021 - 1024<br />
#Sambrook and Russell. 2001. Molecular Cloning A Laboratory Manual. Cold Spring Harbor Laboratry Press. Cold Spring Harbor, New York pg. 1.145. 2007 June.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Traveling_Salesperson_ProblemDavidson Missouri W/Traveling Salesperson Problem2007-09-26T20:55:46Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
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. 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?<br />
<br />
<br />
[[Image:TSP 4N graph.jpg|300px]]<br />
<br />
The graph above shows a modified complete graph with edges leaving the ending node (#4), returning to the start node (#1), and moving from the start to the stop node removed. If we wanted to solve this weighted and directed graph for the shortest path through all nodes, starting at node #1, ending at node #4, and passing through each node only once, we could use our current HPP ''E. coli'' computer construct with one slight modification. <br />
<br><br />
<br><br />
[[Image:TSP 4N shortest.jpg|900px]]<br />
<br />
Instead of putting each half-gene back to back along an edge, we could add in spacers of specified lengths that would allow us to model the various weights in the graph above. These weights would give edges different lengths (in base pairs). After performing PCR on all of the solved plasmids (with primers binding to the promoter and terminator), we would be able to find the shortest path through all of the nodes by running the PCR products on a gel. Because the total length of the genes in any Hamiltonian Path through the graph is a constant, the smallest solved fragment will have the lowest total spacer length and will, therefore, be the solution to the Traveling Salesperson Problem (shown above).<br />
<br><br />
<br><br />
[[Image:TSP 4N longer.jpg|900px]]<br />
<br />
This image shows an alternate route through the graph. The length of this fragment is longer than the length of the solution to the TSP.<br />
<br><br />
<br><br />
[[Image:TSP 4N falsepos.jpg|900px]]<br />
<br />
False positives can also come into play with this construct. However, certain rules can be put into place when choosing spacer lengths to avoid having false positive PCR products that are longer than the true solution.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Controlling_ExpressionDavidson Missouri W/Controlling Expression2007-09-26T20:55:32Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
To solve the Hamiltonian Path Problem our team needs to utilize a mechanism that is capable to transcribing a sequence of adjacent genes downstream of a single promoter region. Due to the "flippable" nature of our construct, inserting a second promoter region downstream of our initial promoter region is not feasible, as we would be unable to insure that a "solved" phenotype was the result of a single path through the graph. Because of our inability to control gene expression downstream of the start of transcription, we searched for promoters of the highest processivity and repressibility. Thanks to the biobrick system we could choose from any operon in the E.Coli genome. <br />
<br />
<br><br />
===The Promoter Tester===<br />
<br> <br />
We will also produce two constructs for tetsing promoters. MWSU will produce (Kan, RFP, Tet) while Davidson will produce (Kan, Tet, RFP). We can drop in different promoters and look for phenotypes. <br />
<br />
[[Davidson Missouri W/PLac| pLac]]<br />
<br> The promoter of the Lac operon was an optimal place to start becuase the kinetics of control are well documented in comparison to most E.Coli operons.<br />
<br />
<br />
[[Image:Promoter_tester.png|750 px]]<br />
<br />
<br />
In addition to pLac we are going to test a lambda model promoter, the ompC porin biobrick promoter, and the T7 RNA Polymerase promoter.<br />
Davidson is also going to have synthesized an improved pLac promoter that is shorter, will have better repression, better induction, and hopefully lack the backwards promotion we have detected with Part: [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. We will test out the modified promoter [http://partsregistry.org/Part:BBa_R0011 BBa_R0011] which is reported to have good repression and strong induction. We may still introduce the UV5 double mutation to enhance transcription and compare with R0010.<br />
<br />
Davidson will also test 8 different promoters from the registry to see if any of them can promote transcription of all three genes in the promoter tester.<br />
<br />
MWSU is also going to produce backwards LacIq to put upstream of pLac [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. The purpose of this is to have more LacIq in the cytoplasm at all times, regardless of ITPG status.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Gene_splittingDavidson Missouri W/Gene splitting2007-09-26T20:55:21Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
We have selected 4 genes to split. We will use our [http://gcat.davidson.edu/iGEM07/genesplitter.html online] gene splitting [[Davidson Missouri W/Web tool| web tool]] to choose the PCR primers. Davidson will produce these 4 split genes and test each one. <br />
<br />
# [[Davidson Missouri W/Gene splitting#Kanamycin|Kanamycin Nucleotidyltransferase]] <br />
# [[Davidson Missouri W/Gene splitting#RFP|Red Fluorescent Protein]]<br />
# [[Davidson Missouri W/Gene splitting#CAT|Chloramphenicol Acetyltransferase]]<br />
# [[Davidson Missouri W/Gene splitting#Cre|Cre Recombinase]]<br />
<br><br />
[[Davidson Missouri W|Return to DMW main page]]<br />
<br><br />
=The Genes=<br />
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"<br />
|-<br />
!style="color: red; background-color: black;" width="5%"| Gene<br />
!style="color: red; background-color: black;" width="65%"| Description<br />
!style="color: red; background-color: black;" width="30%"| Graphic<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Kanamycin Nucleotidyltransferase<br />
|<br />
<span id="Kanamycin"></span>One gene our team will be using as a node in our Hamiltonian Path problem is Kanamycin resistance translated in the form of Kanamycin nucleotidyltransferase (KNTase). The antibiotic Kanamycin, once in the cytosol of E.Coli, inhibits protein synthesis by interacting with the “decoding” region in the small ribosomal subunit RNA.(Sambrook and Russel, 2001) The KNTase enzyme, as a member of the aminoglycoside phosphotransferase (APH) enzyme family, blocks Kanamycin’s ability to inhibit protein synthesis by transferring a nucleoside monophosphate (adenyl) group from Mg2+-ATP to the 4’ hydroxyl group of Kanamycin, inhibiting its ability to bind to the srRNA.<br />
[http://www.ingentaconnect.com/content/els/00452068/1999/00000027/00000005/art91144 1]<br />
<br />
Our goal was to insert a hix site (a polar molecule) in an area of KNTase protein that would not interfere with its ability to inhibit Kanamycin. We looked at mutational analysis of KNTase and other aminoglycoside phosphotransferase enzymes to determine which aspects of KNTase’s structure were integral to its function and therefore not an ideal site for hix site insertion. KNTase is a dimer consisting of 253 amino acids in the molecule [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 3]. In looking at conserved structures in the APH family we took into consideration that:<br />
<br />
-Substitution of AA 190 caused 650-fold decrease in enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 190 is involved in catalysis [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-AA 195 and 208 are involved in Mg2+ binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htmv 5]<br />
<br />
-Mutant Enzymes 190, 205, 210 all showed changes in mg+2 binding from the WT [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-Substitution of AA 210 (conserved) reduced enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 166 serves to catalyze reactions involving ATP [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 44 is involved in ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-AA 60 is involved in orientation of AA 44 and ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-We did not consider any Amino Acids near the N or C terminus <br />
<br />
-We did not consider any residues near ß-sheets or ∂-helices close to the active site because hydrogen bonding plays an active role in substrate stabilization and the polarity of our hix site could disrupt the secondary structure and therefore the hydrogen bonding ability of KNTase) <br />
<br />
|align="center"| [[Image:KNTase_hix_cut.png]] <br>The yellow bands at the top and bottom of the molecule denotes hix site insertion<br />
<br />
We decided to insert our hix sites at the 125 AA of each monomer due to their distance from each other, active site secondary structure, N or C terminus, and lack of any previous mutational analysis proving its function as integral.<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|DsRed - Red Fluorescent Protein<br />
<br />
|<br />
<span id="RFP"></span>We use genes to represent the nodes on our Hamiltonian path. One of the essential features of these genes is that they can tolerate the insertion of a Hix site. It has been previously demonstrated that GFP fluoresces despite a Hix insertion. Another glowing protein, [http://partsregistry.org/Part:BBa_E1010 RFP] (from [http://www.ncbi.nlm.nih.gov/Taxonomy/Browser/wwwtax.cgi?id=86600 ''Discosoma sp.'']), is a candidate for use in our path. Although its DNA sequence is markedly different from GFP's, it has some amino acid similarity and a remarkable structural similarity. Both proteins have a Beta-barrel structure which surrounds an internal chromophore.<br />
<br />
Inserting 13 amino acids into a protein can potentially disrupt its ability to function. It is thus essential to find an insertion point that does not interfere with the protein's function. Fortunately, the similarity between GFP and RFP allows us to make a highly educated guess for where to insert. RFP's amino acid position 154 is homologous to GFP's amino acid position 157, which is where GFP was split. This is therefore our best guess for where to insert the Hix site.<br />
<br />
|align="center"|[[Image:Rfp_hix_insertion_point.jpg|200px]]<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Chloramphenicol Acetyltransferase<br />
|<span id="CAT"></span>[http://partsregistry.org/Part:BBa_P1004 Chloramphenicol Acetyltransferase] was one of the genes we chose as a node for our Hamiltonian Path. It is a bacterial gene that neutralizes the effect of an antibiotic, Chloramphenicol, by transferring acetyl groups to Chloramphenicol and changes its shape into a harmless form.<br />
<br />
The specific Chloramphenicol Acetyltransferase gene we are using comes from the plasmid PSV2CAT whose original source is an ''E. coli'' transposable element Tn9 (Sambrook, 2001) Its PDB ID# is [http://www.pdb.org/pdb/explore/explore.do?structureId=1PD5 1PD5].<br />
<br />
I have chosen to insert my hixC site between amino acid 52 and 53. I chose this point because it is away from the active site of the protein, the point that contains the catalytic binding sites and allow the recognition and binding of the substrate. It is important for the insertion point to be away from the active site because we do not want the overall function and structure of the protein to be destroyed in the process of splitting. We want to split at a point where the two halves of the protein cannot work as single units, but once a hixC site has been inserted, and the two halves are brought back together, the protein displays its original function.<br />
<br />
|align="center"|[[Image: Chlor.jpg|200px]]<br>The structure of a type I Chloramphenicol Acetyltransferase used in the BioBrick Registry.<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Cre Recombinase<br />
|<span id="Cre"></span>We will also attempt to insert a hixC site into the Cre Recombinase gene. Cre Recombinase binds as a dimer to a specific sequence of DNA called a ''loxP'' site. If two ''loxP'' sites are facing in opposite orientations, then Cre Recombinase will flip the section of DNA in between. If two ''loxP'' sites are facing in the same orientation, then Cre Recombinase will excise the DNA in between, creating a new plasmid.<br />
<br />
In researching Cre Recombinase, we found that the gene had already been split by another lab. [http://www3.interscience.wiley.com/cgi-bin/abstract/104558885/ABSTRACT] In the study done by Casanova et al, two independent but overlapping sections of the Cre Recombinase gene were placed in separate locations along an E. Coli chromosome. When translated, the two overlapping halves of the Cre Recombinase protein bound together and formed a functional Cre Recombinase protein.<br />
<br />
In order for Casanova et al's split protein to be functional, the overlapping section of the bound protein at the split site presumably could not significantly hinder the protein’s ability to bind to ''loxP'' sites or recombine DNA segments. With that in mind, we investigated the same region split by Casanova et al. as the prime candidate for the insertion of a hixC site.<br />
<br />
The site that was eventually chosen reflects both the protein structure shown to the right and the previous research done in the Casanova lab. We believe that amino acids 190-191 along the Cre Recombinase protein are unlikely to play a significant role in the functioning of the protein, thus we decided on this location for the insertion of our hixC site.<br />
<br />
Figure 1 on the right depicts a monomer of Cre Recombinase bound to a DNA strand that it is about the cut. Our split site is highlighted in yellow and can be seen far away from the active site of the molecule.<br />
<br />
Figure 2 on the right depicts two dimers of Cre Recombinase coming come together to cut DNA at two ''loxP'' sites. The site of our hixC insertion is highlighted in yellow on each molecule and can be seen far away from the active site.<br />
<br />
|align="center"|[[Image:Cre_recombinase_monomer1.png|200px]]<br><br />
Figure 1<br />
<br />
[[Image:Cre_recombinase_tetramer1.png|200px]]<br><br />
Figure 2</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Mathematical_ModelingDavidson Missouri W/Mathematical Modeling2007-09-26T20:55:05Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
=Markov Chain Model For Flipping=<br />
<br />
'''Does starting orientation matter?'''<br />
<br />
Question: Will the order in which we place the edges in our E.coli computers affect the probability of us detecting a Hamiltonian Path? <br />
<br />
Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip. <br />
<br />
Answer: We developed a Markov Chain model that takes every signed permutation of edges as a state and the connections between these states are found and categorized by our Matlab programs by both the number of edges that need to be flipped to move between those states and categorized by which specific edge needed to be flipped. Further, our Matlab programs creates a transition matrix based on the weights a user enters to bias the probabilities of making different kinds of flips. <br />
<br />
Once this transition matrix is generated we then compute, for each possible starting state, the probability of that starting state transitioning to any of the solved states after x flips given the biasing of different types of flips. When our Markov Chain model is run for more than 2 edges we always observe a convergence of these probabilities no matter what bias we apply. This shows that starting orientation does not matter since the probability of being solved after a large number of flips is the same for each starting orientation. <br />
<br />
This begs the question: what is a large number of flips? Mostly we observe that this convergence occurs in the first 20 flips for three edges and only for very extreme probabilities does this convergence occur after 60 flips. However, as the number of edges increase we can expect this convergence to occur later. This does not appear to be a problem. Our flipping mechanism flips edges very quickly, so quickly that it is hard to measure. Additionally, the diameter of our transition diagrams increases linearly with the number of edges so there is no reason to believe that the number of flips to convergence would increase at more than a linear pace. <br />
<br />
<br />
[[Image:MarkovChaingraph4nod3edg.jpg]]<br />
<br />
<br />
MATLAB programs that we developed using Markov Chains<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fliplength.m 1.Flip Length]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/pureflip.m 2.Pure Flip]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/biasweighter.m 3.Bias Weighter]<br />
<br />
<br />
<br />
<br><br />
= True Positives / False Positives =<br />
<br />
[[Image:5_node-wiki.jpg]] <br />
<br />
True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.<br />
<br />
[[Image:True_positive.jpg]]<br />
<br />
A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.<br />
<br />
[[Image:Fpospic.jpg]]<br />
<br />
<br />
MATLAB programs used to find the false positives:<br />
<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]<br />
<br />
true positives = 384<br />
false positives = 1,362<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]<br />
<br />
true positives = 10,321,920<br />
false positives = 168,006,848<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]<br />
<br />
<br />
Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive. <br />
<br />
[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]<br />
<br />
=Possion Model For the Number of Plasmids=<br />
<br />
<br />
'''How many E.coli computers?''' <br />
<br />
Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it? <br />
<br />
Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip. Note: This has now been shown to be true but it needs to be stated that our math relies on it. <br />
<br />
If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?<br />
<br />
We can use a cumulative Poisson distribution to answer this question. <br />
<br />
Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences. <br />
<br />
For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation. <br />
<br />
Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.<br />
<br />
Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1. <br />
<br />
We can then solve for m depending on how confident we want to be. If we use <br />
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time. <br />
<br />
1 billion E.coli computers fit conveniently into 1 mL of culture.<br />
<br />
<br />
Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.<br />
<br />
[[Image:Plasmidsneeded.jpg]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Solving_the_HPP_in_vivoDavidson Missouri W/Solving the HPP in vivo2007-09-26T20:54:40Z<p>Miwaters: </p>
<hr />
<div><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/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/Software|<span style="color:red">Software</span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
Using the Hin/''HixC'' flipping mechanism, we are developing a bacterial computer which solves a specific mathematical problem, the ''Hamiltonian Path'' problem.<br />
<br />
=The Hamiltonian Path Problem=<br />
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?<br />
<br />
We solve our problem by transforming ''E. coli'' cells with specially engineered plasmids.<br />
<br />
==Designing a Plasmid==<br />
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.<br />
<br />
[[Image:HamiltonianGraph.PNG|thumb|700px|center|Above: A graph on a plasmid. Below: flipping into a solution.]]<br />
<br />
==Developing Nodes==<br />
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|''gene splitting'']]. If our reporter gene tolerates a ''HixC'' insertion then we can use it as a node on our graph.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Resources_and_CitationsDavidson Missouri W/Resources and Citations2007-09-26T20:53:01Z<p>Miwaters: </p>
<hr />
<div><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: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/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/Resources and Citations|<span style="color:black">Resources and Citations</span>]]</center><br />
<br />
=Protocols, Tools and Guidelines=<br />
[[Davidson Missouri W/Davidson_Protocols| Davidson's Wet Lab Protocols]]<br />
<br />
[[Davidson_Missouri_W/MWSU_protocols| Missouri Western's Wet Lab Protocols]]<br />
<br />
[http://gcat.davidson.edu/iGEM07/genesplitter.html Spliting Genes Web Tool]<br />
<br />
[http://www.bio.davidson.edu/courses/Molbio/Protocols/ORIs.html '''Compatibility of Plasmids''']<br />
<br />
[http://tools.wikimedia.de/~tangotango/nubio/ A Site with an FAQ on Wikis]<br />
<br />
[http://spreadsheets.google.com/pub?key=pw-NamR_FPJOfhl6mDrkZcw Davidson Freezer Stocks - iGEM 2007 Project]<br />
<br />
[[Media:VT_Presentation.ppt| Davidson's PPT for VT]]<br />
#'''DMW Part Numbers for 2007 are BBa_I715000 to BBa_I715999.''' <br />
#[http://partsregistry.org/Help:BioBrick_Part_Names How to Name a New Part]<br />
#[http://partsregistry.org/Add_a_Part_to_the_Registry Entering the Part to the Registry]<br />
#[http://partsregistry.org/Help:Part_Features How to Annotate a Part]<br />
<br />
=References=<br />
#Cool site for Breakfast [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml]<br />
#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]<br />
#Bruce Henschen's paper describing one-time flippable Hix sites [http://www.bio.davidson.edu/Courses/genomics/2006/henschen/Bruce_Finalpaper.doc]<br />
#Intro to Hamiltonian Path Problem and DNA [http://www.ams.org/featurecolumn/archive/dna-abc2.html]<br />
#Adleman, LM. Molecular Computation of Solutions To Combinatorial Problems. Science. 11 November 1994. Vol. 266. no. 5187, pp. 1021 - 1024<br />
#Sambrook and Russell. 2001. Molecular Cloning A Laboratory Manual. Cold Spring Harbor Laboratry Press. Cold Spring Harbor, New York pg. 1.145. 2007 June.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Traveling_Salesperson_ProblemDavidson Missouri W/Traveling Salesperson Problem2007-09-26T20:51:38Z<p>Miwaters: </p>
<hr />
<div><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: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/Controlling Expression| <span style="color:red"> Controlling Expression </span>]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
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. 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?<br />
<br />
<br />
[[Image:TSP 4N graph.jpg|300px]]<br />
<br />
The graph above shows a modified complete graph with edges leaving the ending node (#4), returning to the start node (#1), and moving from the start to the stop node removed. If we wanted to solve this weighted and directed graph for the shortest path through all nodes, starting at node #1, ending at node #4, and passing through each node only once, we could use our current HPP ''E. coli'' computer construct with one slight modification. <br />
<br><br />
<br><br />
[[Image:TSP 4N shortest.jpg|900px]]<br />
<br />
Instead of putting each half-gene back to back along an edge, we could add in spacers of specified lengths that would allow us to model the various weights in the graph above. These weights would give edges different lengths (in base pairs). After performing PCR on all of the solved plasmids (with primers binding to the promoter and terminator), we would be able to find the shortest path through all of the nodes by running the PCR products on a gel. Because the total length of the genes in any Hamiltonian Path through the graph is a constant, the smallest solved fragment will have the lowest total spacer length and will, therefore, be the solution to the Traveling Salesperson Problem (shown above).<br />
<br><br />
<br><br />
[[Image:TSP 4N longer.jpg|900px]]<br />
<br />
This image shows an alternate route through the graph. The length of this fragment is longer than the length of the solution to the TSP.<br />
<br><br />
<br><br />
[[Image:TSP 4N falsepos.jpg|900px]]<br />
<br />
False positives can also come into play with this construct. However, certain rules can be put into place when choosing spacer lengths to avoid having false positive PCR products that are longer than the true solution.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Traveling_Salesperson_ProblemDavidson Missouri W/Traveling Salesperson Problem2007-09-26T20:50:57Z<p>Miwaters: </p>
<hr />
<div><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: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/Controlling Expression| <span style="color:red"> Controlling Expression </span>]] [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
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. 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?<br />
<br />
<br />
[[Image:TSP 4N graph.jpg|300px]]<br />
<br />
The graph above shows a modified complete graph with edges leaving the ending node (#4), returning to the start node (#1), and moving from the start to the stop node removed. If we wanted to solve this weighted and directed graph for the shortest path through all nodes, starting at node #1, ending at node #4, and passing through each node only once, we could use our current HPP ''E. coli'' computer construct with one slight modification. <br />
<br><br />
<br><br />
[[Image:TSP 4N shortest.jpg|900px]]<br />
<br />
Instead of putting each half-gene back to back along an edge, we could add in spacers of specified lengths that would allow us to model the various weights in the graph above. These weights would give edges different lengths (in base pairs). After performing PCR on all of the solved plasmids (with primers binding to the promoter and terminator), we would be able to find the shortest path through all of the nodes by running the PCR products on a gel. Because the total length of the genes in any Hamiltonian Path through the graph is a constant, the smallest solved fragment will have the lowest total spacer length and will, therefore, be the solution to the Traveling Salesperson Problem (shown above).<br />
<br><br />
<br><br />
[[Image:TSP 4N longer.jpg|900px]]<br />
<br />
This image shows an alternate route through the graph. The length of this fragment is longer than the length of the solution to the TSP.<br />
<br><br />
<br><br />
[[Image:TSP 4N falsepos.jpg|900px]]<br />
<br />
False positives can also come into play with this construct. However, certain rules can be put into place when choosing spacer lengths to avoid having false positive PCR products that are longer than the true solution.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Controlling_ExpressionDavidson Missouri W/Controlling Expression2007-09-26T20:50:40Z<p>Miwaters: </p>
<hr />
<div><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: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/Controlling Expression| <span style="color:black"> Controlling Expression </span>]] | [[Davidson Missouri W/Traveling Salesperson Problem| <span style="color:red">Traveling Salesperson Problem</span> ]] | [[Davidson Missouri W/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
To solve the Hamiltonian Path Problem our team needs to utilize a mechanism that is capable to transcribing a sequence of adjacent genes downstream of a single promoter region. Due to the "flippable" nature of our construct, inserting a second promoter region downstream of our initial promoter region is not feasible, as we would be unable to insure that a "solved" phenotype was the result of a single path through the graph. Because of our inability to control gene expression downstream of the start of transcription, we searched for promoters of the highest processivity and repressibility. Thanks to the biobrick system we could choose from any operon in the E.Coli genome. <br />
<br />
<br><br />
===The Promoter Tester===<br />
<br> <br />
We will also produce two constructs for tetsing promoters. MWSU will produce (Kan, RFP, Tet) while Davidson will produce (Kan, Tet, RFP). We can drop in different promoters and look for phenotypes. <br />
<br />
[[Davidson Missouri W/PLac| pLac]]<br />
<br> The promoter of the Lac operon was an optimal place to start becuase the kinetics of control are well documented in comparison to most E.Coli operons.<br />
<br />
<br />
[[Image:Promoter_tester.png|750 px]]<br />
<br />
<br />
In addition to pLac we are going to test a lambda model promoter, the ompC porin biobrick promoter, and the T7 RNA Polymerase promoter.<br />
Davidson is also going to have synthesized an improved pLac promoter that is shorter, will have better repression, better induction, and hopefully lack the backwards promotion we have detected with Part: [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. We will test out the modified promoter [http://partsregistry.org/Part:BBa_R0011 BBa_R0011] which is reported to have good repression and strong induction. We may still introduce the UV5 double mutation to enhance transcription and compare with R0010.<br />
<br />
Davidson will also test 8 different promoters from the registry to see if any of them can promote transcription of all three genes in the promoter tester.<br />
<br />
MWSU is also going to produce backwards LacIq to put upstream of pLac [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. The purpose of this is to have more LacIq in the cytoplasm at all times, regardless of ITPG status.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Gene_splittingDavidson Missouri W/Gene splitting2007-09-26T20:50:21Z<p>Miwaters: </p>
<hr />
<div><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: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:black"> 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/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<hr><br />
<br />
We have selected 4 genes to split. We will use our [http://gcat.davidson.edu/iGEM07/genesplitter.html online] gene splitting [[Davidson Missouri W/Web tool| web tool]] to choose the PCR primers. Davidson will produce these 4 split genes and test each one. <br />
<br />
# [[Davidson Missouri W/Gene splitting#Kanamycin|Kanamycin Nucleotidyltransferase]] <br />
# [[Davidson Missouri W/Gene splitting#RFP|Red Fluorescent Protein]]<br />
# [[Davidson Missouri W/Gene splitting#CAT|Chloramphenicol Acetyltransferase]]<br />
# [[Davidson Missouri W/Gene splitting#Cre|Cre Recombinase]]<br />
<br><br />
[[Davidson Missouri W|Return to DMW main page]]<br />
<br><br />
=The Genes=<br />
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"<br />
|-<br />
!style="color: red; background-color: black;" width="5%"| Gene<br />
!style="color: red; background-color: black;" width="65%"| Description<br />
!style="color: red; background-color: black;" width="30%"| Graphic<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Kanamycin Nucleotidyltransferase<br />
|<br />
<span id="Kanamycin"></span>One gene our team will be using as a node in our Hamiltonian Path problem is Kanamycin resistance translated in the form of Kanamycin nucleotidyltransferase (KNTase). The antibiotic Kanamycin, once in the cytosol of E.Coli, inhibits protein synthesis by interacting with the “decoding” region in the small ribosomal subunit RNA.(Sambrook and Russel, 2001) The KNTase enzyme, as a member of the aminoglycoside phosphotransferase (APH) enzyme family, blocks Kanamycin’s ability to inhibit protein synthesis by transferring a nucleoside monophosphate (adenyl) group from Mg2+-ATP to the 4’ hydroxyl group of Kanamycin, inhibiting its ability to bind to the srRNA.<br />
[http://www.ingentaconnect.com/content/els/00452068/1999/00000027/00000005/art91144 1]<br />
<br />
Our goal was to insert a hix site (a polar molecule) in an area of KNTase protein that would not interfere with its ability to inhibit Kanamycin. We looked at mutational analysis of KNTase and other aminoglycoside phosphotransferase enzymes to determine which aspects of KNTase’s structure were integral to its function and therefore not an ideal site for hix site insertion. KNTase is a dimer consisting of 253 amino acids in the molecule [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 3]. In looking at conserved structures in the APH family we took into consideration that:<br />
<br />
-Substitution of AA 190 caused 650-fold decrease in enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 190 is involved in catalysis [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-AA 195 and 208 are involved in Mg2+ binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htmv 5]<br />
<br />
-Mutant Enzymes 190, 205, 210 all showed changes in mg+2 binding from the WT [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-Substitution of AA 210 (conserved) reduced enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 166 serves to catalyze reactions involving ATP [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]<br />
<br />
-AA 44 is involved in ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-AA 60 is involved in orientation of AA 44 and ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]<br />
<br />
-We did not consider any Amino Acids near the N or C terminus <br />
<br />
-We did not consider any residues near ß-sheets or ∂-helices close to the active site because hydrogen bonding plays an active role in substrate stabilization and the polarity of our hix site could disrupt the secondary structure and therefore the hydrogen bonding ability of KNTase) <br />
<br />
|align="center"| [[Image:KNTase_hix_cut.png]] <br>The yellow bands at the top and bottom of the molecule denotes hix site insertion<br />
<br />
We decided to insert our hix sites at the 125 AA of each monomer due to their distance from each other, active site secondary structure, N or C terminus, and lack of any previous mutational analysis proving its function as integral.<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|DsRed - Red Fluorescent Protein<br />
<br />
|<br />
<span id="RFP"></span>We use genes to represent the nodes on our Hamiltonian path. One of the essential features of these genes is that they can tolerate the insertion of a Hix site. It has been previously demonstrated that GFP fluoresces despite a Hix insertion. Another glowing protein, [http://partsregistry.org/Part:BBa_E1010 RFP] (from [http://www.ncbi.nlm.nih.gov/Taxonomy/Browser/wwwtax.cgi?id=86600 ''Discosoma sp.'']), is a candidate for use in our path. Although its DNA sequence is markedly different from GFP's, it has some amino acid similarity and a remarkable structural similarity. Both proteins have a Beta-barrel structure which surrounds an internal chromophore.<br />
<br />
Inserting 13 amino acids into a protein can potentially disrupt its ability to function. It is thus essential to find an insertion point that does not interfere with the protein's function. Fortunately, the similarity between GFP and RFP allows us to make a highly educated guess for where to insert. RFP's amino acid position 154 is homologous to GFP's amino acid position 157, which is where GFP was split. This is therefore our best guess for where to insert the Hix site.<br />
<br />
|align="center"|[[Image:Rfp_hix_insertion_point.jpg|200px]]<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Chloramphenicol Acetyltransferase<br />
|<span id="CAT"></span>[http://partsregistry.org/Part:BBa_P1004 Chloramphenicol Acetyltransferase] was one of the genes we chose as a node for our Hamiltonian Path. It is a bacterial gene that neutralizes the effect of an antibiotic, Chloramphenicol, by transferring acetyl groups to Chloramphenicol and changes its shape into a harmless form.<br />
<br />
The specific Chloramphenicol Acetyltransferase gene we are using comes from the plasmid PSV2CAT whose original source is an ''E. coli'' transposable element Tn9 (Sambrook, 2001) Its PDB ID# is [http://www.pdb.org/pdb/explore/explore.do?structureId=1PD5 1PD5].<br />
<br />
I have chosen to insert my hixC site between amino acid 52 and 53. I chose this point because it is away from the active site of the protein, the point that contains the catalytic binding sites and allow the recognition and binding of the substrate. It is important for the insertion point to be away from the active site because we do not want the overall function and structure of the protein to be destroyed in the process of splitting. We want to split at a point where the two halves of the protein cannot work as single units, but once a hixC site has been inserted, and the two halves are brought back together, the protein displays its original function.<br />
<br />
|align="center"|[[Image: Chlor.jpg|200px]]<br>The structure of a type I Chloramphenicol Acetyltransferase used in the BioBrick Registry.<br />
|-<br />
<br />
|style="color: black; background-color: red;" align="center"|Cre Recombinase<br />
|<span id="Cre"></span>We will also attempt to insert a hixC site into the Cre Recombinase gene. Cre Recombinase binds as a dimer to a specific sequence of DNA called a ''loxP'' site. If two ''loxP'' sites are facing in opposite orientations, then Cre Recombinase will flip the section of DNA in between. If two ''loxP'' sites are facing in the same orientation, then Cre Recombinase will excise the DNA in between, creating a new plasmid.<br />
<br />
In researching Cre Recombinase, we found that the gene had already been split by another lab. [http://www3.interscience.wiley.com/cgi-bin/abstract/104558885/ABSTRACT] In the study done by Casanova et al, two independent but overlapping sections of the Cre Recombinase gene were placed in separate locations along an E. Coli chromosome. When translated, the two overlapping halves of the Cre Recombinase protein bound together and formed a functional Cre Recombinase protein.<br />
<br />
In order for Casanova et al's split protein to be functional, the overlapping section of the bound protein at the split site presumably could not significantly hinder the protein’s ability to bind to ''loxP'' sites or recombine DNA segments. With that in mind, we investigated the same region split by Casanova et al. as the prime candidate for the insertion of a hixC site.<br />
<br />
The site that was eventually chosen reflects both the protein structure shown to the right and the previous research done in the Casanova lab. We believe that amino acids 190-191 along the Cre Recombinase protein are unlikely to play a significant role in the functioning of the protein, thus we decided on this location for the insertion of our hixC site.<br />
<br />
Figure 1 on the right depicts a monomer of Cre Recombinase bound to a DNA strand that it is about the cut. Our split site is highlighted in yellow and can be seen far away from the active site of the molecule.<br />
<br />
Figure 2 on the right depicts two dimers of Cre Recombinase coming come together to cut DNA at two ''loxP'' sites. The site of our hixC insertion is highlighted in yellow on each molecule and can be seen far away from the active site.<br />
<br />
|align="center"|[[Image:Cre_recombinase_monomer1.png|200px]]<br><br />
Figure 1<br />
<br />
[[Image:Cre_recombinase_tetramer1.png|200px]]<br><br />
Figure 2</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Mathematical_ModelingDavidson Missouri W/Mathematical Modeling2007-09-26T20:49:57Z<p>Miwaters: </p>
<hr />
<div><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:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] | [[Davidson Missouri W/Mathematical Modeling| <span style="color:black">Mathematical Modeling</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/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
=Markov Chain Model For Flipping=<br />
<br />
'''Does starting orientation matter?'''<br />
<br />
Question: Will the order in which we place the edges in our E.coli computers affect the probability of us detecting a Hamiltonian Path? <br />
<br />
Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip. <br />
<br />
Answer: We developed a Markov Chain model that takes every signed permutation of edges as a state and the connections between these states are found and categorized by our Matlab programs by both the number of edges that need to be flipped to move between those states and categorized by which specific edge needed to be flipped. Further, our Matlab programs creates a transition matrix based on the weights a user enters to bias the probabilities of making different kinds of flips. <br />
<br />
Once this transition matrix is generated we then compute, for each possible starting state, the probability of that starting state transitioning to any of the solved states after x flips given the biasing of different types of flips. When our Markov Chain model is run for more than 2 edges we always observe a convergence of these probabilities no matter what bias we apply. This shows that starting orientation does not matter since the probability of being solved after a large number of flips is the same for each starting orientation. <br />
<br />
This begs the question: what is a large number of flips? Mostly we observe that this convergence occurs in the first 20 flips for three edges and only for very extreme probabilities does this convergence occur after 60 flips. However, as the number of edges increase we can expect this convergence to occur later. This does not appear to be a problem. Our flipping mechanism flips edges very quickly, so quickly that it is hard to measure. Additionally, the diameter of our transition diagrams increases linearly with the number of edges so there is no reason to believe that the number of flips to convergence would increase at more than a linear pace. <br />
<br />
<br />
[[Image:MarkovChaingraph4nod3edg.jpg]]<br />
<br />
<br />
MATLAB programs that we developed using Markov Chains<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fliplength.m 1.Flip Length]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/pureflip.m 2.Pure Flip]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/biasweighter.m 3.Bias Weighter]<br />
<br />
<br />
<br />
<br><br />
= True Positives / False Positives =<br />
<br />
[[Image:5_node-wiki.jpg]] <br />
<br />
True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.<br />
<br />
[[Image:True_positive.jpg]]<br />
<br />
A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.<br />
<br />
[[Image:Fpospic.jpg]]<br />
<br />
<br />
MATLAB programs used to find the false positives:<br />
<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]<br />
<br />
true positives = 384<br />
false positives = 1,362<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]<br />
<br />
true positives = 10,321,920<br />
false positives = 168,006,848<br />
<br />
[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]<br />
<br />
<br />
Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive. <br />
<br />
[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]<br />
<br />
=Possion Model For the Number of Plasmids=<br />
<br />
<br />
'''How many E.coli computers?''' <br />
<br />
Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it? <br />
<br />
Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip. Note: This has now been shown to be true but it needs to be stated that our math relies on it. <br />
<br />
If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?<br />
<br />
We can use a cumulative Poisson distribution to answer this question. <br />
<br />
Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences. <br />
<br />
For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation. <br />
<br />
Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.<br />
<br />
Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1. <br />
<br />
We can then solve for m depending on how confident we want to be. If we use <br />
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time. <br />
<br />
1 billion E.coli computers fit conveniently into 1 mL of culture.<br />
<br />
<br />
Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.<br />
<br />
[[Image:Plasmidsneeded.jpg]]</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Solving_the_HPP_in_vivoDavidson Missouri W/Solving the HPP in vivo2007-09-26T20:49:38Z<p>Miwaters: </p>
<hr />
<div><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/Mathematical Modeling| <span style="color:red">Mathematical Modeling</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/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
Using the Hin/''HixC'' flipping mechanism, we are developing a bacterial computer which solves a specific mathematical problem, the ''Hamiltonian Path'' problem.<br />
<br />
=The Hamiltonian Path Problem=<br />
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?<br />
<br />
We solve our problem by transforming ''E. coli'' cells with specially engineered plasmids.<br />
<br />
==Designing a Plasmid==<br />
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.<br />
<br />
[[Image:HamiltonianGraph.PNG|thumb|700px|center|Above: A graph on a plasmid. Below: flipping into a solution.]]<br />
<br />
==Developing Nodes==<br />
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|''gene splitting'']]. If our reporter gene tolerates a ''HixC'' insertion then we can use it as a node on our graph.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Background_InformationDavidson Missouri W/Background Information2007-09-26T20:49:12Z<p>Miwaters: </p>
<hr />
<div><center>[[Davidson Missouri W| <span style="color:red">Home</span>]] | [[Davidson Missouri W/Background Information| <span style="color:black">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/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/Resources and Citations|<span style="color:red">Resources and Citations</span>]]</center><br />
<br />
<hr><br />
<br />
In 1994 Adleman developed a system to solve the Hamiltonian Path problem using DNA ''in vitro''. We have implemented a bacterial system to solve Hamiltonian Path problems ''in vivo''. Our bacterial computer works by taking advantage of the Hin Recombinase protein and ''HixC'' sites to perform a "flipping" operation. By strategically placing ''HixC'' sites on a plasmid, along with reporter genes, we can simulate paths on a graph through flipping.<br />
<br />
=The Hin Recombinase/''HixC'' System Revisited=<br />
''Salmonella typhimurium'' is a bacterium which moves using flagella. Depending on its environment, it expresses different sets of surface proteins on its flagella. It is able to change this expression through the use of Hin Recombinase and ''HixC'' sites. The Hin Recombinase enzyme catalyzes the inversion of DNA that lies between a pair of ''HixC'' sites. By flipping DNA segments between ''HixC'' sites ''S. typhimurium'' can express alternate flagellar surface proteins.<br />
<br />
# Given a segment of DNA, flanked by ''HixC'' sites (blue arrow):<br>[[Image:hinhix1.png|thumb|none|800px|Figure 1.]]<br />
# Two dimers of Hin Recombinase protein attach to a pair of ''HixC'' sites around the DNA segment.<br>[[Image:hinhix2.png|thumb|none|800px|Figure 2.]]<br />
# The DNA segment between the pair of ''HixC'' sites is inverted. Note that the green arrow is unaffected.<br>[[Image:hinhix3.png|thumb|none|800px|Figure 3.]]<br />
<br />
=Flipping Pancakes=<br />
In the 2006 iGEM competition, [https://2006.igem.org/wiki/index.php/Davidson_2006 Davidson] and [https://2006.igem.org/wiki/index.php/Missouri_Western_State_University_2006 Missouri Western] used Hix Recombinase and ''HixC'' to model a mathematical problem, called the Pancake Flipping problem. The problem is the following: given a stack of pancakes which are burnt on one side and golden on the other, and two spatulas, what is the minimum number of flips required to sort the stack by pancake size and with all burnt sides facing downwards?<br />
<br />
[[Image:pancake_sorting.gif|frame|none|How many flips does this take?]]<br />
<br />
Using mathematical models it is possible to compute these estimates for small stacks. However, adding pancakes to a stack increases the number of possible permutations non-linearly. The number of possible stacks of ''n'' pancakes is equal to: 2^n (n!). Thus traditional computers are not well-suited for computations involving large pancake stacks.<br />
<br />
However, it is possible to model pancake flipping using bacteria. If each pancake is given an identification number, along with a sign designating its orientation, then this can be stated equivalently using genes. Thus the following images show equivalent notations for pancake stacks:<br />
<br />
[[Image:pancakes_compare.gif|frame|none|A stack of pancakes.]]<br />
<br />
[[Image:DNA_arrows.gif|frame|none|Genes on a plasmid.]]<br />
<br />
By taking advantage of this notation it is possible to use bacteria as computers to solve pancake-flipping problems.<br />
<br />
=Why Use Bacteria?=<br />
<br />
Although we have demonstrated how it is possible to solve mathematical problems using bacteria, it may not be obvious why this is helpful. Due to the exponential increase in problem size that arises from a linear increase in pancake stack size, traditional computers are not good at solving large pancake problems. However, bacterial computers are not affected as much by this problem. If each bacterium contains several plasmids, each plasmid is a computer, and a single flask of bacteria contains millions of bacteria, then it is trivial to produce millions of computers. Each computer will be acting in parallel with the others, drastically reducing the amount of time required to reach a solution. The use of bacterial computers is thus a way to allow us to solve computational problems which traditional computers cannot.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Controlling_ExpressionDavidson Missouri W/Controlling Expression2007-09-26T20:48:01Z<p>Miwaters: </p>
<hr />
<div><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: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/Controlling Expression| <span style="color:black"> 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><br />
<br />
<hr><br />
<br />
To solve the Hamiltonian Path Problem our team needs to utilize a mechanism that is capable to transcribing a sequence of adjacent genes downstream of a single promoter region. Due to the "flippable" nature of our construct, inserting a second promoter region downstream of our initial promoter region is not feasible, as we would be unable to insure that a "solved" phenotype was the result of a single path through the graph. Because of our inability to control gene expression downstream of the start of transcription, we searched for promoters of the highest processivity and repressibility. Thanks to the biobrick system we could choose from any operon in the E.Coli genome. <br />
<br />
<br><br />
===The Promoter Tester===<br />
<br> <br />
We will also produce two constructs for tetsing promoters. MWSU will produce (Kan, RFP, Tet) while Davidson will produce (Kan, Tet, RFP). We can drop in different promoters and look for phenotypes. <br />
<br />
[[Davidson Missouri W/PLac| pLac]]<br />
<br> The promoter of the Lac operon was an optimal place to start becuase the kinetics of control are well documented in comparison to most E.Coli operons.<br />
<br />
<br />
[[Image:Promoter_tester.png|750 px]]<br />
<br />
<br />
In addition to pLac we are going to test a lambda model promoter, the ompC porin biobrick promoter, and the T7 RNA Polymerase promoter.<br />
Davidson is also going to have synthesized an improved pLac promoter that is shorter, will have better repression, better induction, and hopefully lack the backwards promotion we have detected with Part: [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. We will test out the modified promoter [http://partsregistry.org/Part:BBa_R0011 BBa_R0011] which is reported to have good repression and strong induction. We may still introduce the UV5 double mutation to enhance transcription and compare with R0010.<br />
<br />
Davidson will also test 8 different promoters from the registry to see if any of them can promote transcription of all three genes in the promoter tester.<br />
<br />
MWSU is also going to produce backwards LacIq to put upstream of pLac [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. The purpose of this is to have more LacIq in the cytoplasm at all times, regardless of ITPG status.</div>Miwatershttp://2007.igem.org/wiki/index.php/Davidson_Missouri_W/Controlling_ExpressionDavidson Missouri W/Controlling Expression2007-09-26T20:45:12Z<p>Miwaters: </p>
<hr />
<div><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: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/Controlling Expression| <span style="color:black"> 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><br />
<br />
<hr><br />
<br />
To solve the Hamiltonian Path Problem our team needs to utilize a mechanism that is capable to transcribing a sequence of adjacent genes downstream of a single promoter region. Due to the "flippable" nature of our construct, inserting a second promoter region downstream of our initial promoter region is not feasible, as we would be unable to insure that a "solved" phenotype was the result of a single path through the graph. Because of our inability to control gene expression downstream of the start of transcription, we searched for promoters of the highest processivity and repressibility. Thanks to the biobrick system we could choose from any operon in the E.Coli genome. <br />
<br />
<br><br />
===The Promoter Tester===<br />
<br> <br />
We will also produce two constructs for tetsing promoters. MWSU will produce (Kan, RFP, Tet) while Davidson will produce (Kan, Tet, RFP). We can drop in different promoters and look for phenotypes. <br />
<br />
[[Davidson Missouri W/PLac| pLac]]<br />
<br> The promoter of the Lac operon was an optimal place to start becuase the kinetics of control are well documented in comparison to most E.Coli operons.<br />
<br />
<br />
[[Image:Promoter_tester.png|750 px]]<br />
<br />
<br />
<br />
Davidson is also going to have synthesized an improved pLac promoter that is shorter, will have better repression, better induction, and hopefully lack the backwards promotion we have detected with Part: [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. We will test out the modified promoter [http://partsregistry.org/Part:BBa_R0011 BBa_R0011] which is reported to have good repression and strong induction. We may still introduce the UV5 double mutation to enhance transcription and compare with R0010.<br />
<br />
Davidson will also test 8 different promoters from the registry to see if any of them can promote transcription of all three genes in the promoter tester.<br />
<br />
MWSU is also going to produce backwards LacIq to put upstream of pLac [http://partsregistry.org/Part:BBa_R0010 BBa_R0010]. The purpose of this is to have more LacIq in the cytoplasm at all times, regardless of ITPG status.</div>Miwaters