Bacteria-Run Computer Solves Math Puzzle

Gigs of Bacteria

A new living computer, bred from E. coli bacteria instead of stamped from silica, has for the first time successfully solved a classic mathematical puzzle known as the Burnt Pancake Problem.

While this bacteria-based computer is more proof of concept than practical, a living computer might one day solve complex mathematical problems faster than silicon supercomputers.

"The computing potential of DNA far exceeds that of any other material," said Karmella Haynes, a researcher at Davidson University and lead study author. "If we figure out how to increase that capacity in a practical manner we will have much more computing power."

The Burnt Pancake Problem works like this: Imagine you are a diner owner. To promote your delicious fare, you want to create a golden pyramid of pancakes. Using a spatula, you have to rearrange an existing stack of different-sized pancakes, each of which is burned on one side. The aim 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. You want to stack them properly in the fewest number of flips.

If there are only a few pancakes, it's a relatively easy problem to solve. But as the number of pancakes increases, the possible number of solutions skyrockets.

For six pancakes, there are 46,080 possible solutions. For 12 pancakes, there are 1.9 trillion permutations.

A traditional, silica-based computer would run through every single possible solution to the problem, one at a time.

In a biology-based computer, each bacterium becomes a single computer that runs a different part of the problem simultaneously. Since a million bacteria-based computers can fit into a single drop of water, all of them working together could speed up the calculations dramatically.

Obviously E. coli can't flip real pancakes. Instead E. coli flip a section of their DNA. The "spatula" is a protein called flagellin, which was taken from salmonella bacteria and injected into the E. coli bacteria.

In salmonella, flagellin works like an on/off switch, determining which of two proteins will be produced to help hide, and keep alive, the bacteria when it infects an organism. In the computer, the proteins make a bacterium resistant to antibiotics and keep it alive -- but only if it solves the problem. If a bacterium can't solve the problem, i.e. flip the pancake into the correct order, antibiotics kill it.

So far the computer has only solved a two-pancake problem which, admittedly, isn't terribly difficult. Creating bacteria that can solve the Burnt Pancake Problem using multiple pancakes will be difficult, said Haynes.

Once a solution is found, however, it will be cheap to reproduce.

"All it would cost is about a tablespoon of sugar," said Haynes.

Don't expect to see a bacterial super computer at Best Buy any time soon though. According to Tom Knight, a synthetic biologist at the Massachusetts Institute of Technology, "this will open the door to a wide variety of biological computing."

But that includes only simple computing, like telling researchers how many times they have encountered a certain chemical.

"This won't make your Xbox run faster," said Knight.

Original here