May 20, 2008 US researchers have genetically engineered the bacterium E. coli to coax its DNA into computing a classic mathematical puzzle. Molecules of DNA have the natural ability to store and process information, in fact DNA represents the highest storage density of anything on Earth - French cytogeneticist Jerome LeJeune showed that the amount of information in one strand of human DNA is the same as that in 1,000 books of small print, each around 500 pages thick. Scientists have been performing computations with bare DNA molecules in lab dishes since the mid-1990s, but the new research, reported online in the Journal of Biological Engineering, is the first to do DNA computation in living cells.
A research team, which included members from the biology and the mathematics departments of Davidson College, North Carolina and Missouri Western State University, Missouri, were able to create bacterial computers by adding genes to Escherichia coli, (E. coli), bacteria. The potential computational power of programmed bacteria is immense - “Imagine having the parallel processing power of a million computers all in the space of a drop of water, it’s possible to do that because cells are so tiny and DNA is so tiny.” says Karmella Haynes, a biologist at Davidson College. At the moment however, the DNA-computation system that Haynes and her colleagues designed can only solve problems by flipping and sorting data. So while the system might not be running your laptop anytime soon, it is well suited to a classic mathematical problem known as the burnt pancake problem.
The original pancake problem described a waiter navigating a busy restaurant with a stack of various sized pancakes. Wanting to avoid dropping the pancakes, the waiter needs to sort the pancakes in order by size. Having only one free hand, the only available operation is to lift a top portion of the stack, invert it, and replace it. Finding the maximum number of flips needed is the Pancake Problem. In the burnt pancake variation one side of the pancakes is burnt, and the pancakes must be sorted with the burnt side down. It’s the sort of brain teaser that mathematicians love to crack, but it’s also a metaphor for an important problem in computer science - sorting large amounts of data into the right order by repeatedly flipping chunks of data. Knowing the minimum number of flips necessary will tell programmers when their software has been fully optimized to sort the data as quickly as possible.
In this experiment, Haynes and her colleagues used fragments of DNA as the pancakes. They inserted an enzyme, called Hin recombinase, into E. coli enable it to flip the DNA ‘pancakes’ that are marked by genetic flags. The researchers designed these segments so that when the DNA fragments had been flipped into the correct order the DNA spells out the code for a gene that gives the bacterium resistance to an antibiotic. That way, applying the antibiotic to the colony of engineered bacteria killed all of the bacteria that had not yet solved the puzzle. Only those that had “stacked their pancakes” would survive. The time required to reach the mathematical solution in the bugs reflects the minimum number of flips needed to solve the burnt pancake problem.
The engineered bacteria computed the equivalent of two stacked pancakes as a proof of concept, but Haynes says the researchers are now scaling it up to work for more pancakes and working on adapting the technique to work for other, related math problems.
For further info visit the Journal of Biological Engineering.
