GcatWiki - User contributions [en]

Davidson Missouri W/Resources and Citations

2007-08-03T19:21:52Z

Synthetic Students: /* Protocols, Tools and Guidelines */

Davidson Missouri W/Resources and Citations

2007-08-02T18:00:22Z

Synthetic Students: /* Protocols, Tools and Guidelines */

File:VT Presentation.ppt

2007-08-02T17:57:14Z

Synthetic Students: This is the power point presentation that we gave at Virginia Tech.

This is the power point presentation that we gave at Virginia Tech.

Davidson Missouri W/Background Information

2007-07-27T00:53:15Z

Synthetic Students: make images thumbnails

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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.

=The Hin Recombinase/''HixC'' System Revisited=
''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.

# Given a segment of DNA, flanked by ''HixC'' sites (blue arrow): [[Image:hinhix1.png|thumb|none|800px|Figure 1.]]
# Two dimers of Hin Recombinase protein attach to a pair of ''HixC'' sites around the DNA segment. [[Image:hinhix2.png|thumb|none|800px|Figure 2.]]
# The DNA segment between the pair of ''HixC'' sites is inverted. Note that the green arrow is unaffected. [[Image:hinhix3.png|thumb|none|800px|Figure 3.]]

=Flipping Pancakes=
In the 2006 iGEM competition, [http://parts.mit.edu/wiki/index.php/Davidson_2006 Davidson] and [http://parts.mit.edu/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?

[[Image:pancake_sorting.gif|frame|none|How many flips does this take?]]

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.

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:

[[Image:pancakes_compare.gif|frame|none|A stack of pancakes.]]

[[Image:DNA_arrows.gif|frame|none|Genes on a plasmid.]]

By taking advantage of this notation it is possible to use bacteria as computers to solve pancake-flipping problems.

=Why Use Bacteria?=

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.

Davidson Missouri W/Andrew Martens

2007-07-25T16:30:10Z

Davidson Missouri W/Solving the HPP in vivo

2007-07-11T19:48:53Z

Synthetic Students: /* How We Solve it */

Davidson Missouri W/Will DeLoache

2007-07-11T19:47:32Z

Synthetic Students:

[[Image:Will1.jpg]] Will DeLoache

Davidson Missouri W/Will DeLoache

2007-07-11T19:46:35Z

Synthetic Students: Will DeLoache moved to Davidson Missouri W/Will DeLoache

[[Image:Will1.jpg]]Will DeLoache

Will DeLoache

2007-07-11T19:46:35Z

Synthetic Students: Will DeLoache moved to Davidson Missouri W/Will DeLoache

#redirect [[Davidson Missouri W/Will DeLoache]]

Davidson Missouri W

2007-07-11T19:45:28Z

Synthetic Students:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>
 

[[Image:DMW-1.jpg|300px|center]]

<center>
=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;" | Team Logos
! style="color: white; background-color: black;" | Group Photo
|-

|style="color: black; background-color: red;" align="center"| '''Davidson'''

[[Davidson Missouri W/Oyinade Adefuye|Oyinade Adefuye]]
 
[[Davidson Missouri W/Will DeLoache|Will DeLoache]]
 
[[Davidson Missouri W/Jim Dickson|Jim Dickson]]
 
[[Davidson Missouri W/Andrew Martens|Andrew Martens]]
 
[[Davidson Missouri W/Amber Shoecraft|Amber Shoecraft]]
 
[[Davidson Missouri W/Mike Waters|Mike Waters]]


|style="color: black; background-color: red;" align="center"|

[[Davidson Missouri W/A. Malcolm Campbell|A. Malcom Campbell]]
 
[[Davidson Missouri W/Karmella Haynes|Karmella Haynes]]
 
[[Davidson Missouri W/Laurie Heyer|Laurie Heyer]]


|style="color: black; background-color: white;" align="center"|
[[Image:DavidsonLogo.gif]]

|style="color: black; background-color: white;" align="center"|
[[Image:Team1.jpg|thumb|300px]]

|-

|style="color: black; background-color: gold;" align="center"|'''Missouri Western'''

[[Davidson Missouri W/Jordan Baumgardner|Jordan Baumgardner]]
 
[[Davidson Missouri W/Tom Crowley|Tom Crowley]]
 
[[Davidson Missouri W/Lane H. Heard|Lane H. Heard]]
 
[[Davidson Missouri W/Nickolaus Morton|Nickolaus Morton]]
 
[[Davidson Missouri W/Michelle Ritter|Michelle Ritter]]
 
[[Davidson Missouri W/Jessica Treece|Jessica Treece]]
 
[[Davidson Missouri W/Matthew Unzicker|Matthew Unzicker]]
 
[[Davidson Missouri W/Amanda Valencia|Amanda Valencia]]


|style="color: black; background-color: gold;" align="center"|

[[Davidson Missouri W/Todd Eckdahl|Todd Eckdahl]]
 
[[Davidson Missouri W/Jeff Poet|Jeff Poet]]


|style="color: black; background-color: white;" align="center"|[[Image:MWLogo.gif]]

|style="color: black; background-color: white;" align="center"|
|-

|}

 
[[Image:Team_graph.jpg|center|thumb|500px|A Human Representation of Adleman's Graph (see below)]]
 

<center>

=Our Project=
</center>

{| border="1" cellpadding="5" cellspacing="0" align="center" width="90%"
|-
! style="color: black; background-color: red;" width="20%"| In Depth
! colspan="3" style="color: black; background-color: red;" width="60%"| Overview
|-
|style="color: black; background-color: black;" align="center"|
[[Davidson Missouri W/Background Information|Background Information]]
 
[[Davidson Missouri W/Solving the HPP in vivo|Current Project: Solving the Hamiltonian Path Problem ''in vivo'']]
 
[[Davidson Missouri W/Probability and Statistics|Probability and Statistics]]
 
[[Davidson Missouri W/Gene splitting|Gene Splitting]]
 
[[Davidson Missouri W/Controlling Expression|Controlling Expression]]
 
[[Davidson Missouri W/Traveling Salesperson Problem|Traveling Salesperson Problem]]
 
[[Davidson Missouri W/Backwards Promotion and read-through transcription|Backwards Promotion and Read-Through Transcription]]
 
[[Davidson Missouri W/Resources and Citations|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 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|The Adleman graph.]]
 
[[Image:HamiltonianGraph.PNG|thumb|700px|center|A graph implemented on a plasmid.]]

|}

Davidson Missouri W/Jeff Poet

2007-07-11T19:43:42Z

Synthetic Students: Jeff Poet moved to Davidson Missouri W/Jeff Poet

Jeff Poet