Davidson 2006

Figure 1 A scrambled stack of four burnt pancakes.

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 <math>2^n n!</math> 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"

Simulation results for two pancakes, useful for calibrating kinetics of pancake flipping. 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 in Figure 1. Note that pancakes 1 and 2 are negative, indicating that these two pancakes are in the wrong orientation (burnt side up). 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 <math> \binom{n+1}{2} </math> ways to choose a segment: two spatula locations must be chosen from among the n + 1 potential locations. For example, there are <math> \binom{5}{2} = \frac{5!}{3! 2!} = 10 </math> 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.A population of E. coli cells (1015 cells, for instance) each carrying ~100 copies of pancake stacks has astounding parallel processing capacity. Lance, please work on this section.

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 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 pancake" constructs and initial observations
• Read-through from the carrier vector backbone leads to uncontrolled Tet expression and uncontrolled flipping
• New [http://partsregistry.org/Part:BBa_J31009 pSB1A7] vector insulates parts from read-through, but is not compatible with parts carrying double terminators
• Solution: designing pancake constructs without double terminators
• "Two-pancake" constructs
• Dealing with biological equivalence: distinguishing 1,2 from -2,-1 using an RFP reporter
• Updated design

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

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]

iGEM 2006 Jamboree

• Presentation Outline

White Board

• General Questions
• Math Questions
• Biology Questions

Biology Tools (Wet Bench)

• Pancake Parts
• Davidson Protocols
• [http://gcat.davidson.edu/IGEM06/oligo.html Oligo Cuts Optimization]: by Lance Harden
• Papers of Interest

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

• Assembly powerpoint
• Assembly plan
• Western Assembly Plan
• Davidson Assembly Plan

Progress

• Plasmids and Bacteria
• Hix and RE
• Hin and Antibiotic Pancakes
• Ligations