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

the possibilities!

[Brian Gordon]

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.

Misleading

[Anonymous Coward]

I think this is quite misleading since the effort to genetically modify the bacteria is not included in the quantification of how fast the computation is being completed. If programmers are allowed to spend enough time to prepare input data for the fastest possible calculation, it may be just as fast or faster than the bacteria. Even if this is not the case, the overhead of preparing the bacteria should not be ignored.

So?

[pushing-robot]

At best, this seems to be a novel form of analog computer. [wikipedia.org] They have their uses, but calling them "faster than silicon" is very misleading; a soap bubble can solve the mean surface problem [wikipedia.org] but I won't be replacing my Core 2 with one.

   

Re:the possibilities!

[Anonymous Coward]

The advantage? Self-replication. Bacteria are crafted, made to do what they do naturally (replicate to populations of millions or more), and then create answers as a by-product of that replication. This has serious possibilities for streamlining any massive iterative function. Essentially, a biological computer grows to meet the problem at hand, unlike static circuits that must slowly work their way through a potentially massive set of answers. The technology isn't even in its infancy yet, but it's yet another field of development with mind-blowing potential.

Re:this still does not prove p == np

[Anonymous Coward]

The reductions we already have work.

But this still doesn't say anything about P or NP, because those are defined with Turing machines, not soap bubbles.

Hamiltonian path != traveling salesman

[Hitokiri Battousai]

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.

parallel computations only half the battle

[caseih]

Hmm. Deja vu here. DNA was used to solve this exact problem:

http://www.jyi.org/volumes/volume8/issue2/features/srivastava.html [jyi.org]

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.

Re:So?

[pushing-robot]

We don't know these bacteria can't be fooled, either. That's not the point, anyway: An analog computer may be useful. But it will solve the problem by "brute force", taking advantage of the massive parallelism inherent in the real world in the form of molecules or bacteria. It may solve the problem "quickly" in our perception, but it's far from efficient in polynomial time, and it doesn't help in terms of P = NP.

And like any analog computer, these bacteria need to be carefully designed to solve a specific problem. Which makes them utterly unsuited for the everyday tasks we perform on digital computers using general-purpose CPUs.

Re:Summary is overrated

[michelcolman]

Even worse, the colony does not even SOLVE the problem! If you let the bacteria grow enough, you have a pretty high probability of getting a solution. But no guarantee, because it's all probabilistic. If some of the bacteria happen to reach the correct solution, they turn the right color. Which is pretty easy to detect if you're just looking for a big patch of yellow bacteria, but not if there are millions of possibilities and only a few bacteria turned the specific color you are looking for. Sure, you could use resistance to antibiotics instead of colors, and kill off the bad solutions, but still, if no bacteria are left, that does not mean there's no solution. And since the number of possibilities grows exponentially with problem size, so will the required size of the bacterial colony. So forget about solving the HPP with 500 or so nodes. Then, on top of that, DNA is not exactly reliable. Already in this small and simple experiment, unexpected colors like pink etc. turned up.

This is incredibly underwhelming

[xZgf6xHx2uhoAj9D]

Len Adleman did a more impressive DNA computing experiment way back in 1994 [wikipedia.org]. Since then Adleman has stated that DNA computing is a dead end until someone comes up with a huge breakthrough. Well...it would be a huge understatement to say that this E. Coli experiment isn't a breakthrough.

Re:parallel computations only half the battle

[Anonymous Coward]

Now I remember why I still read slashdot. Despite all the "frist post", "hot grits", "in soviet russia", "goatse" and whatever other random bollocks goes on here, you still get real geeks, making real news, posting real insightful comments.

Thanks Andrew for taking the time to read and post here..

It sounds like incredibly interesting work, particularly so for me as a software engineer with a wife who works in the biomed industry. Congrats on the paper!

Also, with reference to the gp post, I thought that the previous (DNA) version of the algorithm was using something like gel electrophoresis to sort the resulting DNA fragments by size (making it relatively easy to find the shortest path).. ??