Davidson 2006

From 2006.igem.org

(Difference between revisions)
Jump to: navigation, search
Line 17: Line 17:
{|
{|
|- valign="top"
|- valign="top"
-
|[[Image:four_pancakes.jpg|thumb|250px|left|'''Figure 1'''  A scrambled stack of four burnt pancakes. ]]In the burnt pancake problem, each pancake is given an orientation by burning one side. Figure 1 shows a scrambled stack of burnt pancakes.  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).  Pancakes are sorted with two spatulas. One spatula is used to lift zero or more pancakes off the top of the stack, while the second spatula flips a stack of one or more of the remaining pancakes.  The pancakes lifted by the first spatula are then returned to the top of the stack.  You can watch [[Media:burnt_pancake.mov a movie]] of the stack in Figure 1 being sorted.  Trial and error is one approach to solving the problem, but how could one compute the quickest solution?
+
|[[Image:four_pancakes.jpg|thumb|250px|left|'''Figure 1'''  A scrambled stack of four burnt pancakes. ]]In the burnt pancake problem, each pancake is given an orientation by burning one side. Figure 1 shows a scrambled stack of burnt pancakes.  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).  Pancakes are sorted with two spatulas. One spatula is used to lift zero or more pancakes off the top of the stack, while the second spatula flips a stack of one or more of the remaining pancakes.  The pancakes lifted by the first spatula are then returned to the top of the stack.  You can watch [[Media:burnt_pancake.ogg a movie]] of the stack in Figure 1 being sorted to see how the puzzle is solved.
-
 
+
-
Our approach is to
+
-
 
+
-
model the problem by representing a pancake stack '''mathematically''' and '''biologically'''. A stack of pancakes can be represented by a series of integers in a certain order (ie. 1, 2, 3 vs. 3, 2, 1) where orientation is represented by a positive or negative value (1 vs. -1). Similarly, a series of DNA segments has a certain order (ie. promoter, coding region 1, coding region 2) and each unit has two possible orientations (plus strand vs. minus strand).
+
<big>'''Approach'''</big><br>
<big>'''Approach'''</big><br>
 +
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.
{|
{|
|- valign="top"
|- valign="top"

Revision as of 05:07, 27 October 2006

Logo.gif

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]
Left to Right: Malcolm, Laurie, Sabriya, Erin and Lance
Solving the Pancake Problem with an E. coli Computer


Our goal is to mathematically model and genetically engineer a biological system that can compute solutions to a puzzle called the burnt pancake problem. 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].


The Burnt Pancake Problem
Our project integrates math and biology using the [http://en.wikipedia.org/wiki/Pancake_sorting pancake problem], a puzzle in which a scrambled series of units (or stack of pancakes) must be shuffled into the correct order. You can try solving [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml a version of the pancake problem] yourself.

Figure 1 A scrambled stack of four burnt pancakes.
In the burnt pancake problem, each pancake is given an orientation by burning one side. Figure 1 shows a scrambled stack of burnt pancakes. 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). Pancakes are sorted with two spatulas. One spatula is used to lift zero or more pancakes off the top of the stack, while the second spatula flips a stack of one or more of the remaining pancakes. The pancakes lifted by the first spatula are then returned to the top of the stack. You can watch Media:burnt_pancake.ogg a movie of the stack in Figure 1 being sorted to see how the puzzle is solved.


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.

Simulation results for two pancakes, useful for calibrating kinetics of pancake flipping.
Math: Our mathematical model for a stack of pancakes is a signed permutation, in which each numerical value represents the pancake size (or desired position in the stack) and the sign represents the orientation. For example, "1, 2, 3, 4" is a stack of four pancakes all in the proper order and orientation. "-2, 4, -1, 3" is a scrambled stack of the same four pancakes, as shown in Figure 1. Here, pancakes 1 and 2 are in the wrong orientation (burnt side up). Lance, please work on this section.
3-D structure of a Hin protein complex bound to DNA. View the interactive [http://www.rcsb.org/pdb/static.do?p=explorer/viewers/jmol.jsp Jmol image] (PDB 1ZR4).
Biology: To flip fragments of DNA, we have reconstituted the Hin/ Hix invertase system 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 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. A population of E. coli cells (1015 cells, for instance) each carrying ~100 copies of pancake stacks has astounding parallel processing capacity.


Methods and Results
Basic parts: Parts used in this project were designed by the [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Davidson Davidson] and [http://partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006partsregistry.org/cgi/partsdb/pgroup.cgi?pgroup=iGEM2006&group=Missouri Missouri Western] iGEM teams
Modeling

  • Modeling the behavior of pancake flipping: deducing kinetics and size biases
  • Using modeling to choose which families of unsolved pancake stacks to start with

Building the Biological System

  • Single pancakes
  • The problems of read-through - uncontrolled Tet expression, uncontrolled flipping
  • New [http://partsregistry.org/Part:BBa_J31009 pSB1A7] vector: insulates, but is not compatible with parts carrying double terminators
  • Designing pancakes without TT's
  • Two pancake constructs
  • Biological equivalence - distinguishing 1,2 from -2,-1 using RFP-RBS, updated panckaes


Conclusions

  • Consequences of devices: data storage, possible application for rearranging transgenes in vivo, proof-of-concept for bacterial computers, first in vivo controlled flipping of DNA??
  • 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

White Board

Biology Tools (Wet Bench)

Math Tools

  • Pancake Simulators, aka The Lancelator (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]

Bio-Math 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]

Assembly Plans

Progress

Retrieved from "http://2006.igem.org/wiki/index.php/Davidson_2006"
Personal tools
Past/present/future years