Davidson Missouri W

From 2007.igem.org

(Difference between revisions)
(→Our Successful Project)
 
(71 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>
-
[https://2007.igem.org/Davidson_Missouri_W/FalsePositiveProgram False Positives]
+
|style="color: black; background-color: white;" align="center"|
 +
[[Image:DavidsonLogo.gif]]
-
[https://2007.igem.org/Davidson_Missouri_W/ProjectsCompleted Projects Completed]
+
|style="color: black; background-color: white;" align="center"|
 +
[[Image:Team1.jpg|thumb|center|300px]]
-
== '''Students''' ==
+
|-
-
[[Image:Logo.gif]]
+
|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>
-
• Will DeLoache, Junior Biology Major,  [mailto:wideloache@davidson.edu]
+
|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>
-
• Oyinade Adefuye, Senior Biology Major,  [mailto:oyinadeadefuye@yahoo.com]
+
|style="color: black; background-color: white;" align="center"|[[Image:MWLogo.gif]]
-
• Jim Dickson, Junior Math and Economics Major,    [mailto:jidickson@davidson.edu]
+
|style="color: black; background-color: white;" align="center"|[[Image:MWSUteam.jpeg|thumb|center|300px]]
 +
|-
-
• Amber Shoecraft, Math Major,  [mailto:amshoecraft@davidson.edu]
+
|}
 +
<br>
 +
<center>
-
• Andrew Martens, Senior Biology Major,  [mailto:anmartens@davidson.edu]
+
=Our Successful Project=
 +
</center>
-
• Michael Waters, Sophomore Biology Major,  [mailto:miwaters@davidson.edu]
+
{| 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.
-
-----
+
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?]])
-
[[Image:Header_01.gif]]
+
<br>
 +
 
 +
[[Image:Adelman.png|thumb|300px|center|The Adleman graph.]]  
 +
<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>
 +
|}
-
• Jordan Baumgardner, Junior Biology, Biochemistry/Molecular Biology Major,  [mailto:jbaumgardner@missouriwestern.edu]
 
-
 
-
• Tom Crowley, Senior Biochemisty/Molecular Biology Major,  [mailto:stc8033@missouriwestern.edu]
 
-
 
-
• Lane H. Heard, Central High School graduate,  [mailto:axenmoon@hotmail.com]
 
-
 
-
• Nickolaus Morton, Junior Chemistry Major,  [mailto:nmorton@missouriwestern.edu]
 
-
 
-
• Michelle Ritter, Junior Mathematics Major,  [mailto:mrr5418@missouriwestern.edu]
 
-
 
-
• 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]]
 
-
 
-
• A. Malcolm Campbell [http://www.bio.davidson.edu/people/macampbell/macampbell.html], Professor, Department of Biology, [mailto:macampbell@davidson.edu]
 
-
 
-
• [http://www.bio.davidson.edu/people/kahaynes/kahaynes.html Karmella Haynes], 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.
 
-
 
-
[[Image:AdelmanGraph.JPG|thumb|300px|center| ]] 
 
<br>
<br>
-
[[Image:Sample_graph.png|thumb|700px|center|]]
+
<center> '''A Human Representation of the Adleman Graph. (mouse over to see the full effect)'''
-
==[[Splitting Genes for HPP]]==
+
<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>
-
==[[Davidson's First HPP Construct]]==
+
<div class="rollover">
-
[[Image:3N graph.jpg|200px]]
+
<center>
 +
<a href="#"></a>
 +
</center>
 +
</div>
 +
</body>
 +
</html>
-
The Davidson team has proposed building the graph shown above in our first attempt at solving the Hamiltonian Path Problem in vivo. (The Missouri Western team will likely build a similar graph, with an edge from node 3 to node 1 but no edge from node 2 to node 1.) 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:3N solved no polymerase.jpg|800px]]
 
-
 
-
This cartoon represents a solved arangement of our proposed construct. Between the two pairs of BioBrick restriction enzyme sites lies a region containing three 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 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 upon promotion from the promoter region. All random walks through the graph will be generated through flipping. However, by using the inducible T7 promoter, no phenotypes will be displayed intially. Only in the presence of T7 RNA polymerase will the T7 promoter allow for transcription. This T7 system has been shown to transcribe long regions of DNA.
 
-
 
-
 
-
[[Image:T7-polymerase plasmid.jpg|400px]]
 
<br>
<br>
-
 
+
<br>
-
All plasmids (now containing random walks through the graph) will first be retransformed into new competent cells that lack Hin protein (and, therefore, their flipping mechanism). Instead, these cells will contain the plasmid shown in the image above, which produces T7 RNA polymerase.
+
<br>
<br>
-
[[Image:3N solved polymerase.jpg|800px]]
+
<hr>
-
 
+
-
T7 RNA polymerase is specific to the inducible T7 promoter on the Hamiltonian graph plasmid. Retransformation of the plasmids, therefore, has the dual effect of stopping flipping of edges and intializing transcription of all "solved" genes. The image above shows a solved plasmid post-retransformation. Both GFP and Kanamycin resistance would be expressed in this cell.
+
-
<br><br>
+
-
[[Image:3N falsepos polymerase.jpg|800px]]
+
-
 
+
-
It is possible for all of the genes in the graph to be expressed (or all of the nodes to be visited), but for a Hamiltonian Path not to exist in the system. A "false positive" of this type is shown above. This path (1->2, 2->1, 2->3) through the graph is not allowed because it demands "teleportation" from node 1 to node 2, and it also visits nodes (2 and 1) multiple times. Because false positives require that at least one extra edge exist in the path through the graph (when compared to true solution of the Hamiltonian Path Problem), the true solution to the HPP will always contain the shortest DNA fragment between the promoter and the terminator of all the positive phenotypes. We will screen out any false positives through PCR and gel electrophoresis.
+
-
 
+
-
==[[Traveling Salesperson Problem?]]==
+
-
 
+
-
== '''Resources / Citations'''==
+
-
 
+
-
[https://2006.igem.org/wiki/index.php/The_What%27s_and_How%27s Davidson's Wet Lab Protocols]
+
-
 
+
-
[https://2007.igem.org/Davidson_Missouri_W/MWSU_protocols Missouri Western's Wet Lab Protocols]
+
-
 
+
-
[http://gcat.davidson.edu/iGEM07/genesplitter.html Spliting Genes Web Tool]
+
-
 
+
-
[http://www.bio.davidson.edu/courses/Molbio/Protocols/ORIs.html '''Compatibility of Plasmids''']
+
-
 
+
-
#'''DMW Part Numbers for 2007 are BBa_I715000 to BBa_I715999.'''
+
-
#[http://partsregistry.org/Help:BioBrick_Part_Names How to Name a New Part]
+
-
#[http://partsregistry.org/Add_a_Part_to_the_Registry Entering the Part to the Registry]
+
-
#[http://partsregistry.org/Help:Part_Features How to Annotate a Part]
+
-
 
+
-
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]
+
-
 
+
-
Adleman, LM. Molecular Computation of Solutions To Combinatorial Problems. Science.  11 November 1994. Vol. 266. no. 5187, pp. 1021 - 1024
+
-
 
+
-
Sambrook and Russell. 2001. Molecular Cloning A Laboratory Manual. Cold Spring Harbor Laboratry Press. Cold Spring Harbor, New York pg. 1.145. 2007 June.
+
-
==[[Literature Research]]==
+
<Previous Section | [[Davidson Missouri W/Background Information | Next Section>]]
 +
</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"