Researchers at two US universities have used burnt pancakes and E.Coli to look at ways of creating more efficient sorting algorithms.
The researchers' study, which was conducted by biologists and mathematicians at Davidson College in North Carolina and Missouri Western State University, is an attempt to use the properties of DNA as a model for certain computer processes. Previously, scientists have looked at whether DNA molecules could help design more compact and efficient methods of data storage. In this new study, the researchers examined whether E. Coli bacteria could be used to accurately solve a sorting algorithm problem known as the "burnt pancake problem".
Some background: a sorting algorithm is a set of instructions that computer programmers use to sort data in a particular order. The burnt pancake problem is a type of sorting problem where an algorithm must sort elements from largest to smallest by flipping them over, much as a cook would flip a stack of differently-sized pancakes.
What makes designing an algorithm for this problem particularly tricky is that before the sorting is complete, all of the elements must be flipped so that one specific side faces upward. In other words, imagine that you have a stack of pancakes where one side is burnt and one side is a perfect golden brown. In the course of sorting all of the pancakes from smallest to largest, you would obviously want to have all the golden sides facing upward at the end of the sort. The goal of designing an algorithm for the burnt pancake problem, therefore, is to get all the pancakes stacked from smallest to largest — with all golden sides facing up — in the fewest possible number of flips.
In this particular attempt at solving the burnt pancake problem, researchers used E. coli bacteria DNA to represent the pancakes. According to Dr Karmella Haynes, the study's lead researcher, bacteria DNA is able to inexpensively replicate tasks that would require a large amount of parallel processing capacity if they were performed on actual computers.
"Since our system operates on living cells, it gives us the advantage of cheap reproduction," Haynes says. "After all, cells already know how to duplicate."
The researchers' experiment works as follows: after incubating a sufficient number of E.coli cells to conduct the experiment, the researchers added genes from the Salmonella typhimurium bacteria to the colony that caused the E.coli DNA to begin "flipping" its elements randomly, similar to how the pancakes in the burnt pancake problem need to be flipped over.
With millions of bacteria flipping randomly at the same time, Haynes says, there is a good chance that at least some of the cells will "flip" their DNA in a particular order. The researchers determined which DNA had been properly sorted by adding a gene to the bacteria that made it resistant to antibiotics when the DNA had flipped in a certain order. After a time, they would apply the antibiotics to the cells to see which ones had correctly solved the burnt pancake problem. The researchers then determined the minimum number of flips required to solve the problem by timing the amount of time it took for bacteria to flip into the correct order.
"Every minute, we'd sample some of the bacteria and then add some antibiotics to it to see if any cells would survive," Haynes says. "Now, if we do that every minute, we expect to find some point in time where some of the cells had solved the problem and stacked their DNA in the correct order. Because the system we developed is so massively parallel, that increases the chance that some of them will get it right by chance."
While all of this may seem somewhat like an abstract solution for an abstract problem, Haynes says that the burnt pancake problem has very real implications for geneticists who are looking to understand the genomic evolution of different species. Because many species are so genetically similar, Haynes says that scientists could use the burnt pancake sorting mechanism to determine how many flips it would take for a cat's DNA to become, say, the same as a monkey's DNA.
"Say you have two species that are really similar, and you want to get a measure of their relatedness," she says. "Because there are an infinite number of possible ways those genomes could have been sorted, you'll want to know the minimum number of flips it takes to get from one genome to the other in order to understand their evolutionary relationship."
Looking at the big picture, Haynes says scientists are still working to understand how DNA can be used to model computing processes, and that she expects that researchers will conduct more projects similar to the burnt pancake problem in the future.
"Researchers are continuously working on ways to exploit the nature of DNA," she says.