| Posted: May 23, 2008 |
Living computer solves Burnt Pancake Problem |
|
(Nanowerk News) A research project by Davidson College scientists and collaborators at Missouri Western State University has constructed a basic "living computer" by genetically altering E. coli bacteria. The work demonstrates that computing in living cells is feasible, opening the door to a number of applications including data storage and as a tool for manipulating genes for genetic engineering.
|
 |
|
The burnt pancake problem involves a stack of pancakes of different sizes, each of which has a golden and a burnt side. The goal is to sort the stack so the largest pancake is on the bottom and all pancakes are golden side up. Each flip reverses the order and the orientation (i.e. which side of the pancake is facing up) of one or several consecutive pancakes. The aim is to stack them properly in the fewest number of flips.
|
|
The Davidson/MWSU researchers used fragments of DNA as the pancakes. They added genes from a different type of bacterium to enable E. coli bacteria to flip the DNA 'pancakes'. They included components of a gene that made the bacteria resistant to an antibiotic, but only when the DNA fragments had been flipped into the correct order. The time required to reach the mathematical solution in the bugs reflects the minimum number of flips needed to solve the burnt pancake problem.
|
|
As the number of pancakes increases, solving this problem quickly becomes very hard. There’s no equation that will give the correct answer; it is necessary to explore all the possible configurations of the stack of pancakes. For six pancakes, there are 46,080 configurations. For 12 pancakes, there are about 1.9 trillion.
|
|
“These problems get so immense that even having a huge network of computers is not enough,” says Karmella Haynes, the lead researcher. "Because the number of bacteria in a colony grows exponentially, a single bacterium engineered to perform the flipping problem in its DNA will soon become several billion or trillion little bacterial computers. Each bacterium in the colony can then compute a separate flipping scenario. These 'bacterial computers' could act in parallel with each other, meaning that solutions could potentially be reached quicker than with conventional computers, using less space and at a lower cost."
|
|
In addition to parallel computation, bacterial computing also has the potential to utilize repair mechanisms and, of course, can evolve after repeated use.
|
|
The open access paper "Engineering bacteria to solve the Burnt Pancake Problem" (pdf download, 895 KB) is available at theJournal of Biological Engineering website.
|
