Engineering bacteria to solve the Burnt Pancake Problem
- Karmella A Haynes1Email author,
- Marian L Broderick4,
- Adam D Brown3,
- Trevor L Butner3,
- James O Dickson2,
- W Lance Harden2,
- Lane H Heard3, 6,
- Eric L Jessen3,
- Kelly J Malloy3,
- Brad J Ogden2,
- Sabriya Rosemond1, 5,
- Samantha Simpson1,
- Erin Zwack1,
- A Malcolm Campbell1,
- Todd T Eckdahl3,
- Laurie J Heyer2 and
- Jeffrey L Poet4
© Haynes et al; licensee BioMed Central Ltd. 2008
Received: 09 December 2007
Accepted: 20 May 2008
Published: 20 May 2008
We investigated the possibility of executing DNA-based computation in living cells by engineering Escherichia coli to address a classic mathematical puzzle called the Burnt Pancake Problem (BPP). The BPP is solved by sorting a stack of distinct objects (pancakes) into proper order and orientation using the minimum number of manipulations. Each manipulation reverses the order and orientation of one or more adjacent objects in the stack. We have designed a system that uses site-specific DNA recombination to mediate inversions of genetic elements that represent pancakes within plasmid DNA.
Inversions (or "flips") of the DNA fragment pancakes are driven by the Salmonella typhimurium Hin/hix DNA recombinase system that we reconstituted as a collection of modular genetic elements for use in E. coli. Our system sorts DNA segments by inversions to produce different permutations of a promoter and a tetracycline resistance coding region; E. coli cells become antibiotic resistant when the segments are properly sorted. Hin recombinase can mediate all possible inversion operations on adjacent flippable DNA fragments. Mathematical modeling predicts that the system reaches equilibrium after very few flips, where equal numbers of permutations are randomly sorted and unsorted. Semiquantitative PCR analysis of in vivo flipping suggests that inversion products accumulate on a time scale of hours or days rather than minutes.
The Hin/hix system is a proof-of-concept demonstration of in vivo computation with the potential to be scaled up to accommodate larger and more challenging problems. Hin/hix may provide a flexible new tool for manipulating transgenic DNA in vivo.
The biological equivalent of a burnt pancake is a functional module of DNA such as a promoter or coding region (Fig. 1a). Similar to burnt pancakes in the BPP, DNA modules have directionality (5' to 3'), require a specific order of the units (e.g., promoter followed by coding region) and can be flipped (cut, inverted, and spliced in vivo by cellular machinery). We designed a modular system in which pancake stacks are assembled from flippable DNA segments. Flipping of the DNA segment "pancakes" is mediated by a Salmonella typhimurium-derived DNA recombination system. In Salmonella, Hin DNA recombinase catalyzes an inversion reaction that regulates the expression of alternative flagellin genes by switching the orientation of a promoter located on a 1 kb invertible DNA segment [9, 10]. Two palindromic 26 bp hix sequences flank the invertible DNA segment and serve as the recognition sites for cleavage and strand exchange. A ~70 bp cis-acting recombinational enhancer (RE) increases efficiency of protein-DNA complex formation . We have reconstituted the genetic elements required for DNA inversion as a collection of modular genetic elements for use in E. coli. Our system is a proof-of-concept genetic computing device that manipulates plasmid DNA processors within living cells.
Results and discussion
Design and construction of a Hin/hix-based DNA recombination system
DNA inversion occurs very rapidly in vitro. Protein-DNA complex assembly, strand cleavage, inversion, and ligation occur in less than 1 minute . Therefore, we engineered Hin/hix inversion to be more tractable to regulation and kinetic studies by decreasing inversion efficiency. Hin was cloned from S. typhimurium by PCR. An ssrA LVA protein degradation tag  was added to the C-terminal DNA binding domain to prevent over accumulation of Hin and to achieve tighter control of DNA inversion. In Salmonella, the a