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

Comments

Summary is overrated

[FooAtWFU]

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.

Re:Summary is overrated

[rubycodez]

the traveling salesmen I know did a lot of fucking on their routes. You must be correct.

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.

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.

So?

[pushing-robot]

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.

   

Re:So?

[rjh]

They can't. Soap bubbles can get misled by local minima just like naive hill-walking algorithms.

Hmm

[parallel_prankster]

So next time I itch it means the bacteria on my skin is trying to prove Fermat's last theorem ?

A-choo!

[flatulus]

Aha!

Ebola solves.....

[stox]

the population problem.

Re:parallel computations only half the battle

[Atmchicago]

I'm one of the co-authors of the paper. Indeed, we were aware of what Adleman had done, and were partly inspired by his idea. However, his method required much more manual labor to do the computing, whereas once we have assembled our genetic sequences, we let the bacteria do the thinking.

The color changes were used to identify those bacteria which found a solution. Ideally other selective markers would also work, such as antibiotic resistance. The big issue is that our system can yield false positives, so depending on your setup some manual checking is required.

The Guardian article is rather misleading and inaccurate. We never had the intention of replacing your desktop PC, nor do we claim that our 3-node implementation is faster than a computer (in fact, someone spending 10 minutes or less can figure out a 3-node problem). I'm more excited about the proof-of-concept: we can encode a mathematical problem by using a molecule, hand it to a living organism, and get a correct output. The work was also done by undergraduate students in under a year. We presented our work at iGEM 2007, for those interested.

Cheers,

Andrew Martens