I, Computer

Scientists have built the first living computer and tasked it with solving an important problem: flipping pancakes.

Researchers genetically engineered the bacterium E. coli to coax its DNA into computing a classic mathematical puzzle known as the burned pancake problem. Molecules of DNA have the natural ability to store and process information, and 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.

“Imagine having the parallel processing power of a million computers all in the space of a drop of water,” says Karmella Haynes, a biologist at Davidson College in North Carolina. “It’s possible to do that because cells are so tiny and DNA is so tiny.”

While the potential computational power of programmed bacteria is immense, the DNA-computation system that Haynes and her colleagues designed can only solve problems by flipping and sorting data. It doesn’t have the open-ended computing flexibility of a laptop computer or even a solar-powered calculator, so the bacteria can only handle a limited set of mathematical problems. “We’re not going to have bacteria running iPods just yet,” Haynes says.

Other kinds of DNA computation are possible, though. Researchers in Israel recently designed DNA molecules that could compute games of tic-tac-toe, for example. “I liken this to where video games were when Pong first came out,” says Jeffrey Poet, a mathematician at Missouri Western State University in St. Joseph, Mo., and member of the research team.

The burned pancake problem sounds deceptively simple. Start with a stack of pancakes of varying sizes burned on one side, and try to get the pancakes into order from largest to smallest — all burned side down — through a series of flips. The figurative spatula can flip at any point in the stack, but has to include all the pancakes above. The question mathematicians try to answer is, for a given number of pancakes starting in a random orientation, what’s the smallest number of flips necessary to put the pancakes in order?

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.

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,” Haynes says. 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.

The flipping is done by an enzyme taken from the salmonella bacterium. When salmonella invades a body, the person’s immune system learns to recognize a certain protein on the bacterium’s surface. By flipping a segment of its DNA — which involves snipping out a length of the stringlike molecule, turning that snippet around and reattaching it backward — salmonella can switch to a different version of this protein that the person’s immune system doesn’t recognize, thus evading attack.

Haynes and her colleagues inserted this enzyme, called Hin recombinase, into E. coli. The enzyme could then flip segments of E. coli’s DNA that are marked by genetic flags. The researchers designed these segments so that, when lined up in the correct order like pancakes stacked from biggest to smallest (burned side down, of course), 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. Measuring how long it took the bacteria to reach the solution indicated how many flips were required.

“It’s a neat idea,” comments Lloyd Smith, a bioanalytical chemist at the University of Wisconsin–Madison who has done research on DNA computation. But the challenge for this technique, as for the entire field of DNA computation, will be scaling it up to solve larger problems, Smith says. “One question is how you program a living cell to do something, the other question is how well it scales.”

In this experiment, 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. The researchers are also designing the bacteria to light up with a green fluorescent protein upon solving the puzzle, and the team is adapting the technique to work for other, related math problems.

"We’re right at the beginning,” Poet says. “We’re trying to understand what’s possible.”

[Via Science News]