Applying bacteria to solve the Burnt Pancake Problem

The Burnt Pancake Problem — a mathematical problem whose history Simon Singh recently put in context, in an article in The Guardian — can be attacked by using bacteria. This paper explains how:

“Engineering bacteria to solve the Burnt Pancake Problem,” Karmella A. Haynes [pictured here], Marian L. Broderick, Adam D. Brown, Trevor L. Butner, James O. Dickson, W. Lance Harden, Lane H. Heard, et al., Journal of Biological Engineering, vol. 2, no. 8, 2008, pp. 1-12. (Thanks to investigator Patrick Boyle for bringing this to our attention.) The authors report:

“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.”

Here’s detail from the study: