## Bacteria-based computer cracks classic math puzzle

May 29th, 2008 - 5:32 pm ICT by adminWashington , May 29 (ANI): Living computers may soon solve the most complex mathematical problems much faster than the existing silicon supercomputers.

And now a new E. coli bacteria bred computer has for the first time proved successful in solving a classic mathematical puzzle known as the Burnt Pancake Problem.

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

The Burnt Pancake Problem is: Imagine you are a diner owner and you want to create a golden pyramid of pancakes to promote your delicious fare. Now, you have to use a spatula to rearrange an existing stack of different-sized pancakes, each of which is burned on one side. The catch, however, is that the stack must be sorted in such a way that the largest pancake is on the bottom and all pancakes are golden side up.

Now, with each flip, the order and the orientation (i.e. which side of the pancake is facing up) of one or several consecutive pancakes is reversed and you are required to stack them properly in the fewest number of flips possible.

The problem is a lot easier if the number of pancakes is small, but as the number of pancakes increases, the possible number of solutions is also elevated. In case of six pancakes, there are 46,080 possible solutions, while for 12 pancakes, there are 1.9 trillion permutations.

Normally, a traditional, silica-based computer would try-out every single possible solution to the problem, one at a time. But in case of a biology-based computer, each bacterium becomes a single computer that deals with a different part of the problem simultaneously. As a million bacteria-based computers can be incorporated in a single drop of water, all of them working together could speed up the calculations dramatically.

Evidently, its not possible for E. coli to flip real pancakes, thus its just flips a section of their DNA. Here, a protein called flagellin, taken from salmonella bacteria and injected into the E. coli bacteria, acts as the spatula.”

Now, in case of salmonella, flagellin acts as an on/off switch, and find out 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 impart the bacterium resistance from antibiotics and help it to stay alive provided it solves the problem. In case the bacterium can’t solve the problem, i.e. flip the pancake into the correct order, it is killed by the antibiotics.

Till date, the computer has only solved a two-pancake problem which is not that difficult to achieve. Haynes said that creating bacteria that can solve the Burnt Pancake Problem using multiple pancakes will be difficult. And once a solution is found, however, it will be cheap to reproduce.

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

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

However, it mainly deals with simple computing, like telling researchers how many times they have encountered a certain chemical.

“This won’t make your Xbox run faster,” said Knight. (ANI)

Tags: bacterium, based computer, based computers, classic math, classic mathematical puzzle, computing power, davidson university, delicious fare, discovery news, drop of water, e coli bacteria, golden pyramid, living computers, math puzzle, mathematical problems, pancakes, possible solution, power discovery, single computer, study author