Davidson 2006

From 2006.igem.org

(Difference between revisions)
Jump to: navigation, search
 
(383 intermediate revisions not shown)
Line 1: Line 1:
-
<center>[[Image:logo.gif]]</center>
+
{| cellpadding="10" width="900px"
 +
|- valign="top"
 +
| <center>[[Image:logo.gif]]<br>http://www.davidson.edu<br><br><big>'''[[#overview|Project Overview]]'''<br><br>'''[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson Parts]'''<br><br>'''[[#members|Team Members]]'''<br><br>'''[[#tools|Tools and Resources]]'''<br><br>Check out our [http://www.bio.davidson.edu/courses/synthetic/photos/FlapJack_HotCakes.html Official Team Photo]<br><br>
 +
<font color = red>NEW</font> [[Davidson's Awards]] and [[Photo Gallery]] from iGEM Jamboree 2006</big></center>
 +
| [[Image:igem_team_web.jpg|thumb|450px|Left to Right: Lance, Erin, Samantha, Sabriya, Karmella, Laurie, Malcolm]]
 +
|}
 +
 
 +
----
 +
{| width="900px"
 +
|- valign="top"
 +
|<font size=4><div id="overview">Solving the Pancake Problem with an ''E. coli'' Computer</div></font>
 +
[http://2006.igem.org/Image:IGEM2006T_Davidson.ppt PowerPoint Presentation] and [http://2006.igem.org/Image:IGEM2006_Davidson_poster.ppt Poster]
 +
|-
 +
|Our goal is to genetically engineer a biological system that can compute solutions to a puzzle called the burnt pancake problem. The '''E.HOP computer''' is a proof of concept for computing ''in vivo,'' with implications for future data storage devices and transgenic systems. Our work was done in collaboration with the [http://2006.igem.org/wiki/index.php/Missouri_Western_State_University_2006 Missouri Western iGEM Team] and an undergraduate research fellow from [http://www.hamptonu.edu/ Hampton University].
 +
|[[image:EHOP.gif|250px]]
 +
|}
-
== '''Students''' ==
+
====The Burnt Pancake Problem====
 +
{| width="900px"
 +
|- valign="top"
 +
|The [http://en.wikipedia.org/wiki/Pancake_sorting pancake problem] is a puzzle in which a scrambled series of units (or stack of pancakes) must be shuffled into the correct order and orientation. You can try solving [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml a simple version of the pancake problem] yourself.<br><br>In the burnt pancake problem, each pancake is given an orientation by burning one side. To solve the problem, every unit, or pancake, must be placed in the proper order (largest on bottom, smallest on top) and in the proper orientation (burnt side down, golden side up).  The pancakes are flipped with two spatulas: one to lift pancakes off the top of the stack, the other to flip part (or all) of the remaining stack of pancakes.  The pancakes lifted by the first spatula are returned to the top of the stack without being flipped.  Figure 1 illustrates how the puzzle is solved. 
 +
|-
 +
|[[Image:solving4cakes.jpg|thumb|600px|center|'''Figure 1.''' A scrambled stack of four burnt pancakes, sorted into correct order and orientation in 3 flips. Proper orientation is indicated by solid color, improper orientation by hatched color. ]]
 +
|}
-
• Sabriya Rosemond [mailto:fizzle6821@yahoo.com] is a rising junior biology major at Hampton University in VA.
+
==== Approach ====
 +
{| width="900px"
 +
|- valign="top"
 +
| Trial and error is one approach to solving the burnt pancake problem, but how could one compute the quickest solution? Our idea is to let E. coli do the work, using each cell as a tiny processor in a massively parallel machine.  A mathematical model of the flipping process helps us design the system and interpret the output of our EHOP computer.
 +
|- valign="top"
 +
|[[Image:Jmol_Hin_tetrad_DNA.gif|thumb|250px|left|'''Figure 2.''' 3-D structure of a Hin protein complex bound to DNA. View the [http://www.rcsb.org/pdb/explore/explore.do?structureId=1ZR4 interactive 3-D Jmol image].]]'''Biological System:''' The biological representation of a pancake is a functional unit of DNA such as a promoter or coding region. To flip these units of DNA, we have reconstituted the Hin/ Hix invertase system (Figure 2) from ''Salmonella typhimurium'' as a BioBrick compatible system in ''E. coli''. '''Hin invertase''' (<partinfo>J31001</partinfo>) was cloned from ''S. typhimurium'', Ames strain TA100 and tagged with LVA. We built the recombinational enhancer (RE) and Hin invertase recognition sequence HixC using the publicly available genomic sequence of ''S. typhimurium'' and [http://gcat.davidson.edu/IGEM06/oligo.html a dsDNA assembly program we created] for gene synthesis from overlapping oligos.  
-
• Erin Zwack [mailto:erzwack@davidson.edu] is a rising junior biology major at Davidson College in NC.  
+
Every segment of DNA flanked by a pair of HixC sites is a "pancake" capable of being inverted. Hin invertase recognizes pairs of HixC sites and inverts the DNA fragment in between the two HixC sites with the help of the Fis protein bound to the RE. In our system, selectable phenotypes (including antibiotic resistance and RFP expression), depend upon the proper arrangement of a series of HixC-flanked DNA segments in a plasmid. This allows us to select for cells that have successfully solved the puzzle. An example of a sorted stack of two pancakes is shown in Figure 3.  There are 7 other configurations of 2 pancakes.  If we increase the number of pancakes to 4, there are 384 configurations.  In general, there are 2<sup>n</sup> n! configurations of ''n'' pancakes, a combinatorial explosion of possibilities.  How many should we build and test?  Which ones are most informative?  We need a mathematical model to help answer this question.
-
• Lance Harden [mailto:laharden@davidson.edu] is a rising sophomore at Davidson College, who might major in math.
+
|- valign="top"
 +
|[[Image:biocake.jpg|thumb|400px|right|'''Figure 3.''' A sorted stack of two biological "pancakes"]]
-
== '''Faculty''' ==
+
'''Mathematical Model:''' Our mathematical representation of a stack of pancakes is a '''signed permutation''', in which each numerical value represents the pancake size and the sign of the number represents the orientation. For example, (1, 2, 3, 4) is a sorted stack of four pancakes, all in the proper order and orientation, and (-2, 4, -1, 3) is the scrambled stack of four pancakes shown on the far left of Figure 1. Note that pancakes 1 and 2 are negative, indicating that these two pancakes are in the wrong orientation (burnt side up).
-
• A. Malcolm Campbell [http://www.bio.davidson.edu/campbell Department of Biology], [mailto:macampbell@davidson.edu]
+
[[Image:two_pancake_families.jpg|thumb|400px|right|'''Figure 4.''' Simulation results for two pancakes]]  We simulated the flipping process by assuming that each segment of DNA flanked by Hix sites is equally likely to be flipped by Hin invertase. In an ''n''-pancake stack, there are <sub>n+1</sub>C<sub>2</sub> ways to choose a segment: two spatula locations must be chosen from among the ''n'' + 1 potential locations. For example, there are <sub>5</sub>C<sub>2</sub>  = 5! 3! / 2! = 10 different ways to perform a single flip in a stack of 4 pancakes. The random flipping process continues until the stack is sorted in the correct order and orientation, or until we artificially stop the random flipping process. Figure 4 shows the percent of plasmids that we expect to be sorted after 1 flip, 2 flips, and so on, up to 20 flips, for each of the eight initial configurations.  
-
• Laurie J. Heyer [http://www.davidson.edu/math/heyer/ Department of Mathematics], [mailto:laheyert@davidson.edu]
+
From these simulations, and similar results for stacks of 3 and 4 pancakes, we discovered that the probability of a plasmid being sorted after ''k'' flips was determined by how many ways the solution could be obtained. Several initial configurations had essentially the same graph in our simulations because they had the same number of ways of being sorted.   Only '''one''' representative from each of these "families" of initial configurations needs to be built and tested.  
 +
|}
 +
{| width="900px" cellpadding="5" border="1" border-style="solid" border-color="blue"
 +
|-
 +
| align="center" colspan="4"| <big>'''Methods and Results'''</big><br>The following is an outline of what the Davidson team will present at iGEM 2006
 +
|- valign="top"
 +
| width="300px" | <big>'''Basic parts'''</big><br><br>
 +
Parts used in this project were designed by two iGEM Teams
 +
*[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson]
 +
*[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Missouri Missouri Western]<br><br>
 +
<big>'''Modeling'''</big><br><br>
 +
*[[Modeling pancake flipping]]: deducing kinetics and size biases
 +
*[[Choosing constructs]]: deciding which unsorted pancake stacks to start with
 +
*[[The effect of plasmid copy number]]
 +
| width="300px" | <big>'''Building the Biological System'''</big><br><br>
 +
* [[DNA Pancake|Defining a DNA pancake]] - what parts are flippable?
 +
* [[Read Through Transcription Problem|Read-through from the carrier vector backbone]] leads to uncontrolled Tet expression and uncontrolled flipping
 +
* [[pSB1A7| New vector insulates parts from read-through]], but is not compatible with parts carrying double terminator B0015
 +
* [[pSB1A7 Cloning Solution| Cloning solution]] - design pancake constructs without double terminator B0015
 +
* [[Biological Equivalence Problem|Dealing with biological equivalence]] - distinguishing 1,2 from -2,-1 using an RFP reporter
 +
* [[Two Pancake Stacks|Two-pancake stacks]] - final design
 +
| width="300px" | <big>'''Conclusions'''</big><br><br>
 +
*'''[[Consequences of devices]]'''
 +
** Practical: proof-of-concept for bacterial computers, data storage
 +
** Basic research: transgene rearrangement in vivo, insights into evolution that has occurred via DNA rearrangements
 +
*'''[[Next steps]]''': can solve problem but need control over kinetics
 +
*'''[[Lessons learned]]''':
 +
**Troubleshooting, communication, teamwork, publicity
 +
**Math and Biology meshed really well and even uncovered a new proof
 +
**Multiple campuses can increase capacity through communication and cooperation
 +
**Size of school is not a limiting factor
 +
**We had a blast and learned heaps!!!
 +
|}
 +
----
 +
<font size=4><div id="members">TEAM MEMBERS</div></font>
-
== '''Papers of Interest''' ==
+
'''Students'''
 +
* [mailto:fizzle6821@yahoo.com|  Sabriya Rosemond] is a junior biology major at Hampton University.
 +
* [mailto:erzwack@davidson.edu| Erin Zwack] is a junior biology major at Davidson College.
 +
* [mailto:laharden@davidson.edu| Lance Harden] is a sophomore math major at Davidson College.
 +
* [mailto:sasimpson@davidson.edu| Samantha Simpson] is a sophomore at Davidson College who might design a major in genomics.
-
[http://www.bio.davidson.edu/courses/synthetic/papers/Sanders_04.pdf Stepwise Dissection of the Hin-catalyzed Recombination Reaction from Synapsis to Resolution. Erin R. Sanders and Reid C. Johnson]
+
'''Faculty'''
 +
* [mailto:macampbell@davidson.edu| A. Malcolm Campbell] [http://www.bio.davidson.edu/campbell Department of Biology]
 +
* [mailto:laheyer@davidson.edu| Laurie J. Heyer] [http://www.davidson.edu/math/heyer/ Department of Mathematics]
 +
* [mailto:kahaynes@davidson.edu| Karmella Haynes] [http://www.bio.davidson.edu/ Department of Biology - teaching postdoc and visiting assistant professor]
-
• [http://www.molcells.org/home/journal/article_read.asp?volume=16&number=3&startpage=377 The Effects of Ethidium Bromide and Mg++ Ion on Strand Exchange in the Hin-mediated Inversion Reaction. Hee Jung Lee et al.] Excellent description of Hin recombination mechanism.
+
----
-
• [http://www.jbc.org/cgi/reprint/267/16/11183 The Effects of Symmetrical Recombination Site hixC on Hin Recombinase Function. Heon Man Lim et al.]
+
<font size=4><div id="tools">Tools and Resources</div></font>
-
• [http://www.pubmedcentral.gov/articlerender.fcgi?tool=pubmed&pubmedid=3457367 The role of the loxP spacer region in P1 site-specific recombination. Ronald H.Hoess et al.]
+
{| width="840px" cellpadding="5" border="0"
-
 
+
|- valign="top"
-
[http://www.biomedcentral.com/1471-2164/7/73 A high-throughput screen identifying sequence and promiscuity characteristics of the loxP spacer region in Cre-mediated recombination. Perseus I Missirlis et al.]
+
| width="210px" | <big>'''iGEM 2006 Jamboree'''</big><br><br>
-
 
+
*[[Presentation Outline]]
-
[http://nar.oxfordjournals.org/cgi/content/full/30/13/2764 Non-contact positions impose site selectivity on Cre recombinase. Andreas W. Rufer and Brian Sauer]
+
*[http://2006.igem.org/Image:IGEM2006T_Davidson.ppt PowerPoint Presentation]
-
 
+
*[http://2006.igem.org/Image:IGEM2006_Davidson_poster.ppt Poster] - ppt file
-
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=103771 Growth Phase-Dependent Variation in Protein Composition of the Escherichia coli Nucleoid]
+
| width="210px" | <big>'''White Board'''</big><br><br>
-
 
+
* [[General Questions]]  
-
<br>
+
* [[Math Questions]]
-
 
+
* [[Biology Questions]]
-
=='''Project Description'''==
+
| width="210px" | <big>'''Assembly Plans'''</big><br><br>
-
<br>
+
*[[Assembly powerpoint]]
-
<br>
+
*[[Assembly plan]]
-
<center>[[Image:E_hop.jpg]]</center>
+
*[[Western Assembly Plan]]
-
<br>
+
*[[Davidson Assembly Plan]]
-
<center>
+
*[[pLac Tet Pancake Plan]] (new)
-
<br>
+
| width="210px" | <big>'''Progress'''</big><br><br>
-
<b>Questions to Resolve</b>
+
*[[Plasmids and Bacteria]]
-
</center>
+
*[[Hix and RE]]
-
'''General'''
+
*[[Hin and Antibiotic Pancakes]]
-
 
+
*[[Ligations]]
-
• What is our team name and project name?<br>
+
|- valign="top"
-
<u>ERIC</u> What is HU?<br>
+
| width="210px" | <big>'''Wet Lab Tools'''</big><br><br>
-
# Heat Unstable Nucleoid Protein
+
*[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson Parts]
-
# HU stimulates trascription using lambda phage template
+
*[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Missouri Missouri Western Parts]
-
# It is made of 2 subunits: HU alpha and HU beta
+
*Summer 2006 [[Pancake Parts]]
-
# It is an abundant non-specific DNA binding protein which is highly conserved between
+
*[[The What's and How's| Davidson Protocols]]
-
prokaryotes
+
*[http://gcat.davidson.edu/IGEM06/oligo.html Oligo Cuts Optimization]: by Lance Harden
-
# About 30,000 to 55,000 HU molecules per cell exist in the exponentially growing cells of E. coli W3110.  Indicating that HU, together with Fis, forms a major nucleoid component in the growing E. coli cell
+
*[[Papers of Interest]]
-
# Considered prokaryotic homolog of eukaryotic histones which restrains DNA supercoils in the nucleoid
+
*[[Freezer Stocks]]
-
# Certain fraction of HU is associated with ribosomes
+
| width="210px" | <big>'''Simulators'''</big><br><br>
-
# At saturation, HU dimers may be associated, on average, every 300 to 400 bp of the E. coli genome
+
*<font color='red'>T</font color><font color='blue'>h</font color><font color='orange'>e</font color><font color='silver'> L</font color><font color='sky blue'>a</font color><font color='magenta'>n</font color><font color= 'orange'>c</font color><font color='green'>e</font color><font color=cyan>l</font color><font color='red'>a</font color><font color='brown'>t</font color><font color='blue'>o</font color><font color='violet'>r</font color> Pancake Flipping Simulator(MATLAB Code)
-
# Upon entry into the stationary phase, the HU level started to decrease gradually, decreasing to less than one-third of the maximum level in the late stationary phase
+
* Other Flipping Simulators
-
# Recombination reaction is more dependant on HU when there is a large space between the enhancer and the recombination site
+
**[http://gcat.davidson.edu/IGEM06/randompancakeflipper.m User-Friendly Version]
-
 
+
**[http://gcat.davidson.edu/IGEM06/powerflipper.m Power-User Version]
-
<u>KELLY</u> What is the recombinase enhancer (RE; function, sequence, usual position, relationship with HU, etc.)?<br>
+
**[http://gcat.davidson.edu/IGEM06/powerflipperplus.m Power-User Update]
-
• What sort of spacing can RE allow and still work?<br>
+
**[http://gcat.davidson.edu/IGEM06/findmin.m Findmin]
-
• Will we need more than one RE to accomplish recombination at all positions?<br>
+
**[http://gcat.davidson.edu/IGEM06/bigtrial.m Bigtrial]
-
•      <u>TREVOR</u> What is FIS?
+
| width="210px" | <big>'''Graphing Tools'''</big><br><br>
-
# Factor for Inversion Stimulation
+
*[http://gcat.davidson.edu/IGEM06/pancakeplotter.m Pancakeplotter]
-
# Nucleoid-associated Protein
+
*[http://gcat.davidson.edu/IGEM06/permplotter.m Permplotter]
-
# Exponential growth phase at maximum, decreases to undetectable levels stationary phase
+
*[http://gcat.davidson.edu/IGEM06/adjmat.m Adjmat - creates adjacency matrices]
-
# Binds every 200-300 bases of DNA on average
+
*[http://gcat.davidson.edu/IGEM06/bioadjmat.m Bioadjmat - Adjmat with biological equivalence]
-
# Highly expressed FIS does negative feedback
+
*[http://gcat.davidson.edu/IGEM06/make_radial.m Make_radial - creates a radially-embedded graph]
-
 
+
*[http://gcat.davidson.edu/IGEM06/find_diam.m Find_diam - finds the diameter of a pancake graph]
-
'''Math'''
+
| width="210px" | <big>'''Miscellaneous Computation Tools'''</big><br><br>
-
 
+
*[http://gcat.davidson.edu/IGEM06/signedperms.m Signedperms - lists all signed permutations for a stack of k pancakes]
-
* What is the problem we are solving?<br>
+
*[http://gcat.davidson.edu/IGEM06/bioperms.m Bioperms - Signedperms with biological equivalence]
-
* Can we determine more than just Even/Odd number of flips?<br>
+
|}
-
* What is the distribution of the number of flips required, if each flip is random?<br>
+
-
* What designs might allow us to track flips made?<br>
+
-
* Can we  model the distance of RE from pancake vs. time or number of flips<br>
+
-
* Can we model the kinetics of n flips?<br>
+
-
* Is it possible to simulate the impact of one-time flipping lox/hix sites?<br>
+
-
* Help us design the fewest number of constructs that will allow us to scale up the number of flips in our constructs (1, 2, 3, 4...n)
+
-
 
+
-
'''Biology'''
+
-
 
+
-
<u>ERIN</u> How can we turn Hin off quickly (using CRE or mutating HIX so that they stop after one reversal)?<br>
+
-
<u>B-RAD</u> Do we want to be able to turn Hin on and off more than once?[[Answer]]<br>
+
-
• Should we create a transgenic E. coli with Hin and/or Cre in the chromosome so we won't need so many plasmids?<br>
+
-
• How can we count the number of Flips? (even vs. odd only?)<br>
+
-
<u>SABRIYA</u> Does CRE flip once and is then done with that pancake, or will it be excised the next time?<br>
+
-
• How many flips would the normal negative supercoiling of a plasmid in ''E. coli'' allow?  <br>
+
-
• <u>B-RAD</u> Can we alter the amount of negative supercoiling and thus the number of flips if necessary?[[Answer]] <br>
+
-
• What happens to supercoiling if we make the plasmid larger? <br>
+
-
• What happens to supercoiling during the stationary phase, relax? <br>
+
-
• <u>T-ODD (the biologist formerly known as EckDizzle)</u> Can we apply EtBr to relax the number of supercoils and thus stop recombination?<br>
+
-
For in vitro recombination, < 10 mM Mg++ and 30% glycerol traps reaction after DNA cleavage and 2 uM EtBr slows strand exchange.  Doubtful that these conditions could be established in E coli.<br>
+
-
• What should we use as the reporters? Fluorescent vs. Resistant pancake or combinations?<br>
+
-
• Possible detection delays for both methods and how to minimize the delays<br>
+
-
• Where would biobricks be located?<br>
+
-
• How can we gradually scale up the number of flips with the fewest number of constructs?<br>
+
-
<u>ADAM</u> Can we use mutated lox or hix sites that will allow only single flips?<br>
+
-
• <u>T-ODD</u> Will a segment flip multiple times or will the enzymes move to new sites?<br>
+
-
   
+
-
'''Assembly Issues'''
+
-
 
+
-
• What is the list of DNA parts that we will need for the first stage, second stage, entire project?<br>
+
-
• Which DNA parts exist in the registry? <br>
+
-
• Which DNA parts will have to be designed?  Will they be synthesized or produced by PCR? <br>
+
-
• Which plasmids will be used from the registry? <br>
+
-
• <u>MALCOLM</u> What is the protocol for assembly for the first stage (restriction digestions, ligations, transformations)? <br>
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/reagents.html Common molecular reagents]]
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/magnesium.html PCR and Mg<sup>2+</sup> concentration]]
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/pourgel.html Pouring an agarose gel]]
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/molwt.html Calculate MWs]]
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/digestion.html Digest DNA with restriction enzymes]]
+
-
# [[http://www.bio.davidson.edu/courses/Molbio/Protocols/gels2002/1kbladder.pdf 1kb MW markers]]
+
-
# Shrimp alkaline phosphatase URL to come
+
-
# Ligation URL to come
+
-
# Transformation URL to come
+
-
# Promega miniprep URL to come
+
-
 
+
-
 
+
-
Here's what we'd like to see on your wiki page(s):
+
-
 
+
-
#  A list of all team members, their roles, and email addresses
+
-
# Overview of project(s), including schematics and figures
+
-
# Ongoing data/updates about project(s), including schematics, figures, test data, and biobrick parts used
+
-
# Some photos of your team, facilities, institution, etc.
+
-
# Optionally, anything that broadcasts your team's personality, spirit, sense of fun, or coolness...
+

Latest revision as of 19:12, 19 February 2007

Logo.gif
http://www.davidson.edu

Project Overview

[http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson Parts]

Team Members

Tools and Resources

Check out our [http://www.bio.davidson.edu/courses/synthetic/photos/FlapJack_HotCakes.html Official Team Photo]

NEW Davidson's Awards and Photo Gallery from iGEM Jamboree 2006
Left to Right: Lance, Erin, Samantha, Sabriya, Karmella, Laurie, Malcolm

Solving the Pancake Problem with an E. coli Computer

[http://2006.igem.org/Image:IGEM2006T_Davidson.ppt PowerPoint Presentation] and [http://2006.igem.org/Image:IGEM2006_Davidson_poster.ppt Poster]

Our goal is to genetically engineer a biological system that can compute solutions to a puzzle called the burnt pancake problem. The E.HOP computer is a proof of concept for computing in vivo, with implications for future data storage devices and transgenic systems. Our work was done in collaboration with the [http://2006.igem.org/wiki/index.php/Missouri_Western_State_University_2006 Missouri Western iGEM Team] and an undergraduate research fellow from [http://www.hamptonu.edu/ Hampton University]. EHOP.gif

The Burnt Pancake Problem

The [http://en.wikipedia.org/wiki/Pancake_sorting pancake problem] is a puzzle in which a scrambled series of units (or stack of pancakes) must be shuffled into the correct order and orientation. You can try solving [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml a simple version of the pancake problem] yourself.

In the burnt pancake problem, each pancake is given an orientation by burning one side. To solve the problem, every unit, or pancake, must be placed in the proper order (largest on bottom, smallest on top) and in the proper orientation (burnt side down, golden side up). The pancakes are flipped with two spatulas: one to lift pancakes off the top of the stack, the other to flip part (or all) of the remaining stack of pancakes. The pancakes lifted by the first spatula are returned to the top of the stack without being flipped. Figure 1 illustrates how the puzzle is solved.
Figure 1. A scrambled stack of four burnt pancakes, sorted into correct order and orientation in 3 flips. Proper orientation is indicated by solid color, improper orientation by hatched color.

Approach

Trial and error is one approach to solving the burnt pancake problem, but how could one compute the quickest solution? Our idea is to let E. coli do the work, using each cell as a tiny processor in a massively parallel machine. A mathematical model of the flipping process helps us design the system and interpret the output of our EHOP computer.
Figure 2. 3-D structure of a Hin protein complex bound to DNA. View the [http://www.rcsb.org/pdb/explore/explore.do?structureId=1ZR4 interactive 3-D Jmol image].
Biological System: The biological representation of a pancake is a functional unit of DNA such as a promoter or coding region. To flip these units of DNA, we have reconstituted the Hin/ Hix invertase system (Figure 2) from Salmonella typhimurium as a BioBrick compatible system in E. coli. Hin invertase () was cloned from S. typhimurium, Ames strain TA100 and tagged with LVA. We built the recombinational enhancer (RE) and Hin invertase recognition sequence HixC using the publicly available genomic sequence of S. typhimurium and [http://gcat.davidson.edu/IGEM06/oligo.html a dsDNA assembly program we created] for gene synthesis from overlapping oligos.

Every segment of DNA flanked by a pair of HixC sites is a "pancake" capable of being inverted. Hin invertase recognizes pairs of HixC sites and inverts the DNA fragment in between the two HixC sites with the help of the Fis protein bound to the RE. In our system, selectable phenotypes (including antibiotic resistance and RFP expression), depend upon the proper arrangement of a series of HixC-flanked DNA segments in a plasmid. This allows us to select for cells that have successfully solved the puzzle. An example of a sorted stack of two pancakes is shown in Figure 3. There are 7 other configurations of 2 pancakes. If we increase the number of pancakes to 4, there are 384 configurations. In general, there are 2n n! configurations of n pancakes, a combinatorial explosion of possibilities. How many should we build and test? Which ones are most informative? We need a mathematical model to help answer this question.

Figure 3. A sorted stack of two biological "pancakes"

Mathematical Model: Our mathematical representation of a stack of pancakes is a signed permutation, in which each numerical value represents the pancake size and the sign of the number represents the orientation. For example, (1, 2, 3, 4) is a sorted stack of four pancakes, all in the proper order and orientation, and (-2, 4, -1, 3) is the scrambled stack of four pancakes shown on the far left of Figure 1. Note that pancakes 1 and 2 are negative, indicating that these two pancakes are in the wrong orientation (burnt side up).

Figure 4. Simulation results for two pancakes
We simulated the flipping process by assuming that each segment of DNA flanked by Hix sites is equally likely to be flipped by Hin invertase. In an n-pancake stack, there are n+1C2 ways to choose a segment: two spatula locations must be chosen from among the n + 1 potential locations. For example, there are 5C2 = 5! 3! / 2! = 10 different ways to perform a single flip in a stack of 4 pancakes. The random flipping process continues until the stack is sorted in the correct order and orientation, or until we artificially stop the random flipping process. Figure 4 shows the percent of plasmids that we expect to be sorted after 1 flip, 2 flips, and so on, up to 20 flips, for each of the eight initial configurations.

From these simulations, and similar results for stacks of 3 and 4 pancakes, we discovered that the probability of a plasmid being sorted after k flips was determined by how many ways the solution could be obtained. Several initial configurations had essentially the same graph in our simulations because they had the same number of ways of being sorted. Only one representative from each of these "families" of initial configurations needs to be built and tested.

Methods and Results
The following is an outline of what the Davidson team will present at iGEM 2006
Basic parts

Parts used in this project were designed by two iGEM Teams

  • [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson]
  • [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Missouri Missouri Western]

Modeling

Building the Biological System

Conclusions

  • Consequences of devices
    • Practical: proof-of-concept for bacterial computers, data storage
    • Basic research: transgene rearrangement in vivo, insights into evolution that has occurred via DNA rearrangements
  • Next steps: can solve problem but need control over kinetics
  • Lessons learned:
    • Troubleshooting, communication, teamwork, publicity
    • Math and Biology meshed really well and even uncovered a new proof
    • Multiple campuses can increase capacity through communication and cooperation
    • Size of school is not a limiting factor
    • We had a blast and learned heaps!!!

TEAM MEMBERS

Students

  • Sabriya Rosemond is a junior biology major at Hampton University.
  • Erin Zwack is a junior biology major at Davidson College.
  • Lance Harden is a sophomore math major at Davidson College.
  • Samantha Simpson is a sophomore at Davidson College who might design a major in genomics.

Faculty

  • A. Malcolm Campbell [http://www.bio.davidson.edu/campbell Department of Biology]
  • Laurie J. Heyer [http://www.davidson.edu/math/heyer/ Department of Mathematics]
  • Karmella Haynes [http://www.bio.davidson.edu/ Department of Biology - teaching postdoc and visiting assistant professor]

Tools and Resources
iGEM 2006 Jamboree

  • Presentation Outline
  • [http://2006.igem.org/Image:IGEM2006T_Davidson.ppt PowerPoint Presentation]
  • [http://2006.igem.org/Image:IGEM2006_Davidson_poster.ppt Poster] - ppt file
White Board

Assembly Plans

Progress

Wet Lab Tools

  • [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson Parts]
  • [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Missouri Missouri Western Parts]
  • Summer 2006 Pancake Parts
  • Davidson Protocols
  • [http://gcat.davidson.edu/IGEM06/oligo.html Oligo Cuts Optimization]: by Lance Harden
  • Papers of Interest
  • Freezer Stocks
Simulators

  • The Lancelator Pancake Flipping Simulator(MATLAB Code)
  • Other Flipping Simulators
    • [http://gcat.davidson.edu/IGEM06/randompancakeflipper.m User-Friendly Version]
    • [http://gcat.davidson.edu/IGEM06/powerflipper.m Power-User Version]
    • [http://gcat.davidson.edu/IGEM06/powerflipperplus.m Power-User Update]
    • [http://gcat.davidson.edu/IGEM06/findmin.m Findmin]
    • [http://gcat.davidson.edu/IGEM06/bigtrial.m Bigtrial]
Graphing Tools

  • [http://gcat.davidson.edu/IGEM06/pancakeplotter.m Pancakeplotter]
  • [http://gcat.davidson.edu/IGEM06/permplotter.m Permplotter]
  • [http://gcat.davidson.edu/IGEM06/adjmat.m Adjmat - creates adjacency matrices]
  • [http://gcat.davidson.edu/IGEM06/bioadjmat.m Bioadjmat - Adjmat with biological equivalence]
  • [http://gcat.davidson.edu/IGEM06/make_radial.m Make_radial - creates a radially-embedded graph]
  • [http://gcat.davidson.edu/IGEM06/find_diam.m Find_diam - finds the diameter of a pancake graph]
Miscellaneous Computation Tools

  • [http://gcat.davidson.edu/IGEM06/signedperms.m Signedperms - lists all signed permutations for a stack of k pancakes]
  • [http://gcat.davidson.edu/IGEM06/bioperms.m Bioperms - Signedperms with biological equivalence]
Personal tools
Past/present/future years