Slashdot Mirror
Bacterial Computer Solves Hamiltonian Path Problem
Rob writes "A team of US scientists has engineered bacteria that can solve complex mathematical problems faster than anything made from silicon. The research, published today in the Journal of Biological Engineering (abstract and provisional PDF), proves that bacteria can be used to solve a puzzle known as the Hamiltonian Path Problem, a special case of the traveling salesman problem. The researchers say that this proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems."
According to the abstract, the bacteria presently only solved the problem for a 3-node directed graph. Maybe someday it will be "faster than anything made from silicon", but... not right now.
The World Wide Web is dying. Soon, we shall have only the Internet.
Wait, where's the advantage? OK so it's more efficient but can you run experiments over and over on the same hardware for a decade without repair? Is it scalable? I doubt it's feasible to have a Beowulf cluster of billion-dollar laboratories complete with post-grads to set up and write up reports analyzing each experiment. I'd like to see a schematic for a high-speed bacterial coupler before I start buying cycles on yogurt.
At best, this seems to be a novel form of analog computer. They have their uses, but calling them "faster than silicon" is very misleading; a soap bubble can solve the mean surface problem but I won't be replacing my Core 2 with one.
How can I believe you when you tell me what I don't want to hear?
So next time I itch it means the bacteria on my skin is trying to prove Fermat's last theorem ?
Aha!
the population problem.
"To those who are overly cautious, everything is impossible. "
Now when you say that your computer died, you may be speaking literally...
Soap bubbles can be misled by local minima just like hill-walking algorithms. The problem with soap bubble computation is that when it hits a stable state -- how do you know it's stable? For all you know it's going to collapse further in a few seconds.
Repeat after me: the "soap bubbles can solve the smallest surface problem" meme is wrong as a matter of physics, and wrong as a matter of computer science.
TFA oversimplifies by claiming that finding a Hamiltonian path solves the traveling salesman problem of finding the shortest path. The traveling salesman problem deals with variable edge lengths instead of just finite/infinte, and therefore requires a bit more complex implementation to solve (although they are both still NP-complete).
I would be more impressed if they found the shortest path on an undirected graph with variable length edges.
Hmm. Deja vu here. DNA was used to solve this exact problem:
http://www.jyi.org/volumes/volume8/issue2/features/srivastava.html
It should be noted, however, that even though the DNA would be able to compute the routes in a massively parallel fashion, you still would have to search all the solutions to identify the shortest one, so that kind of defeats the purpose of it. Unless the DNA or the bacteria could compute all the results _and_ identify the correct and optimal answer, then as far as we are concerned the problem is still gotta be close to NP complete (IE strands of DNA to check go up exponentially with problem size). Sounds like these bacteria change color, so maybe that helps reduce the size of the answer set.
E.coli his a very common bacterium with a large family of strains, only a few of which are particularly dangerous to a healthy human (and few more are harmful only to people who are in not-so-good good condition such as the elderly or people with serious illness particularly those with an immune system targeting disease or those weakened by chemotherapy).
Get ready to panic: you almost certainly have a couple of strains of e.coli throughout your intestine right now. Everyone does. As do most warm-blooded animals. It really is that common and generally harmless.
The strain you are presumably most concerned about, as it is one that has hit the headlines a number of times in the last decade or so, is O157:H7 which is a common agent in food poisoning outbreaks. 157/7 is a nasty bugger, and a hardy one too, but I doubt the researchers in this story are using it when there are so many much less troublesome varieties to play with.
E.coli is often use in research like this because its genetics relatively simple and so it is relatively well understood, meaning it is more predictable so experiments are less likely to misfire in surprising ways. It is also comparatively stable (unlike some bacteria and other organisms that mutate every second sneeze). I very much doubt they are working with a strain that is in any way dangerous to a human, and E.coli is not transmitted by air so even if some of the cells in a bacterial computer mutate into a more deadly type they are not going to harm you unless you eat the thing directly or your food comes into contact with it.