Slashdot Mirror

← Back to Stories (view on slashdot.org)

Bacterial Computer Solves Hamiltonian Path Problem

Posted by kdawson on from the sicken-you-or-solve-your-problems dept.

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

5 of 135 comments (clear)

  1. Summary is overrated by FooAtWFU · · Score: 5, Informative

    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.
    1. Re:Summary is overrated by rubycodez · · Score: 5, Funny

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

  2. Hmm by parallel_prankster · · Score: 5, Funny

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

  3. Ebola solves..... by stox · · Score: 5, Funny

    the population problem.

    --
    "To those who are overly cautious, everything is impossible. "
  4. Re:parallel computations only half the battle by Atmchicago · · Score: 5, Interesting

    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

    --

    You can lead a horse to water, but you can't make it dissolve.