Living computers solve complex math puzzle

cientists have genetically tweaked E. coli bacteria to create simple computers capable of solving a classic math puzzle, commonly called the “Burnt Pancake Problem.”

The resulting advance in synthetic biology, according to researchers, hints at the ability of tiny “living computers” to aid in data storage, evolutionary comparisons and even tissue engineering.

The mathematical problem imagines pancakes of varying sizes stacked in random order — each with a burnt side and a golden brown side. The solution requires using the minimum number of manipulations to stack the pancakes according to size, with their burnt sides all facedown. Each manipulation involves flipping one or more pancakes, reversing both their order and orientation. Scientifically, the flipping process is known as sorting by reversals and is the sort of challenge whose complexity increases dramatically with every added pancake. By the time the stack reaches 11, the problem becomes “extremely hairy,” said Karmella Haynes, a visiting adjunct professor of biology at Davidson College in Davidson, N.C.

“It’s kind of like that computer in ‘The Hitchhiker’s Guide to the Galaxy,’ ” she said, referring to a popular novel by the late Douglas Adams. “It’s been working on a problem so long that by the time it comes up with an answer, everybody forgot the question.”

At that level of complexity, “bacteria could probably outperform a conventional computer at solving the problem,” said Haynes, the lead author of a new study suggesting exactly that.

Bacteria as tiny computers
Since 2000, multiple studies have focused on the largely untapped potential for bacteria, yeast and mammalian cells to be harnessed as tiny and abundant computers. “Ours is unique in that the operation required to solve the problem takes place in a living cell,” Haynes said.

The unique in vivo system takes advantage of the remarkable storage capacity of DNA and the efficiency of molecular self-assembly, Haynes said. DNA replication and bacterial cell division can quickly create millions or even billions of parallel processors. “The more little computers you have working on the problem,” she said, “the greater the likelihood that one is going to pick the right path that will take you to the right solution.” ...

To construct the eight possible solutions for how to flip two DNA “pancakes,” the group introduced both the Hin invertase enzyme and the DNA sequences it recognizes into E. coli, creating 100 distinct DNA components and intermediates in the process. In nature, Hin invertase can cut and flip a single section of DNA. For the project, the group showed that the enzyme can flip one piece, an adjacent piece or both at the same time. When correctly ordered and oriented, the combined DNA pieces were designed to reconstitute a gene allowing E. coli to grow even in the presence of the antibiotic tetracycline.

Unexpectedly, the researchers found that even some scrambled DNA arrangements confer tetracycline resistance. The wrinkle, Haynes said, underscores the need for researchers working on larger “pancake stacks” to find a reliable calling card — a distinct color change or survival of the bacteria, for instance — only when the right combination has been achieved amid a host of possibilities. Several of the project’s participants are now working toward that goal. msnbc