5324451
story
Comments: 135 +- Science: Bacterial Computer Solves Hamiltonian Path Problem on Sunday July 26 2009, @12:11AM
Posted
by
kdawson
on Sunday July 26 2009, @12:11AM
from the sicken-you-or-solve-your-problems dept.
from the sicken-you-or-solve-your-problems dept.
background: url(//a.fsdn.com/sd/topics/topicbiotech.gif); width:42px; height:65px;
biotech
background: url(//a.fsdn.com/sd/topics/topicscience.gif); width:62px; height:75px;
science
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."
Related Stories
Submission: bacterial computer solves Hamiltonian path problem by Anonymous Coward
One person's error is another person's data.
All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2010 Geeknet, Inc.
Summary is overrated (Score:5, Informative)
Re:Summary is overrated (Score:4, Insightful)
Parent
Re: (Score:2)
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.
To be fair, current computation is also essentially probabilistic. Solid state electronics like those based on transistors depend on statistical thermodynamic effects for their operation - it just turns out that the probability of a random fluctuation that causes unpredictable behaviour is small enough to be essentially zero - in principle with enough bacteria you could achieve similar levels of confidence.
The scale issue is a real one though, if your base unit is a bacterium instead of an electron you hav
Re: (Score:2)
Also, imagine using this method to solve a problem for which you didn't already know the solution. What exactly are the characteristics of the "correct answer"? Unknown.
In order to be useful, you must engineer a mapping of the possible solutions to genetics in a way where the solution is obvious without knowing what it will be beforehand. That sounds quite difficult. Maybe we could program some bacteria to find out how to do that.
Re: (Score:3, Funny)
It is a fucking special case of the fucking traveling salesman problem. Look, you fucking make a fucking edge of fucking infinite cost for any fucking edge not fucking present in the original fucking graph. Is the fucking shortest fucking tour finite? Fucking Christ on a fucking goddamn stick. Fuck!
Re:Summary is overrated (Score:5, Funny)
the traveling salesmen I know did a lot of fucking on their routes. You must be correct.
Parent
Re: (Score:3, Funny)
Re: (Score:3, Interesting)
Next up... (Score:2, Funny)
the possibilities! (Score:5, Insightful)
Re: (Score:2, Insightful)
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
cue terminator joke in five, four, three... (Score:2, Funny)
The (bacterial computing) Funding Bill is passed. The (colony) goes on-line August 4th, (2017). Human decisions are removed from strategic defense. (The colony) begins to learn at a (exponential) rate. (They) become self-aware at 2:14 a.m. Eastern time, August 29th. In a panic, (humans) try to (feed them antibiotics.)
So? (Score:5, Insightful)
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:So? (Score:5, Informative)
Parent
Re: (Score:3, Insightful)
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 specif
Re: (Score:3, Interesting)
If you've ever looked at a diagram of how a CPU implements DIV or MUL for floating point numbers, then you wouldn't think that the brute force approach would necessarily be so bad. Take a look at size, scale, and cost of ENIAC and then come tell me a Petri dish is "slow and inefficient". Silicon takes advantage of massive speed of serial operations inh
Re: (Score:2)
Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.
They are neither "smart" or stupid. They are just machines that blithely follow instructions.
Re: (Score:2)
Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.
They are neither "smart" or stupid. They are just machines that blithely follow instructions.
... i.e. they are stupid.
No, they are extremely efficient (Score:2)
That doesn't mean they are good at everything, but at what they ARE good at, they are exceedingly efficient. Digital computers are extremely efficient at crunching numbers. At their core, that is ALL they do, and they do it really, really well. Not only are they very quick at it, but they do it right, and they can show you their work. What I mean is that given a set of inputs, the produce a reliable set of outputs. You can also trace through all intermediate steps and watch the state at every step. They are
Re: (Score:2)
Hmm (Score:5, Funny)
Re: (Score:2, Funny)
Re: (Score:2)
...I have discovered a truly marvellous proof of this, which this scrawny geek is too narrow to contain
Wonderful! (Score:3, Funny)
Also, e. coli, really? I hope that, if this technology reaches the stage of commercial use, they've found something better. Or we're gonna hear a constant litany of people complaining that their computer is a piece of crap. It'll be worse than the "cat with a computer mouse" cartoons.* It will.
*Which is why I'm making the joke early and beating the rush.
A-choo! (Score:5, Funny)
Aha!
And we thought... (Score:2)
licking keyboards [slashdot.org] were bad.
Ebola solves..... (Score:5, Funny)
the population problem.
Bacteria Driven Computers? - Slant (Score:2)
Greg Bear wrote a book called Slant [amazon.com] that I read in the late 90's, featuring a biologically driven computer that met the claims of this experiment. While the reality is far from "faster than silicon", sci-fi has the fantasy covered.
My Computer Died (Score:4, Funny)
Good news for stinky nerds (Score:3, Funny)
It has always been the case (Score:2)
Let us remember that the entire world was created from microscopic life forms, not by computers. The life forms learned from the environment and evolved in ways which even the most sophisticated computer would have an impossible time understanding. Let us remember that computers are, by a long shot, not the most efficient problem solvers. For instance, no computer can recognize patterns as well as a human being. The control system governing a hummingbird flight is way more advanced than that of the greatest
Re: (Score:2)
Nature can only follow the laws of physics, which just so happen to be definable mathematically.
Hypothetically, all of this universe could be a simulation, running on some sort of computer. http://en.wikipedia.org/wiki/Simulated_reality/ [wikipedia.org] It's not something I personally subscribe to but I think that asserting some sort of fundemental divide between nature and math/computing is quite foolish.
Also, please keep on brushing your teeth ;)
Turing complete? (Score:2, Funny)
Lets hype over it when it can run Linux
Hamiltonian path != traveling salesman (Score:3, Insightful)
I would be more impressed if they found the shortest path on an undirected graph with variable length edges.
Re: (Score:3, Informative)
Well, Since both the Hamilton path problem and the traveling salesman problem are NP-complete, there exists a polynomial time reduction of one problem into the other. So if you could solve the Hamilton path problem efficiently, and wanted to solve an instance of the traveling salesman problem (or the satisfiability problem, or the integer programming problem, or the partition problem, or whatever other NP-complete problem you might imagine), all you'd have to do is use the polynomial-time reduction to conv
parallel computations only half the battle (Score:4, Insightful)
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:parallel computations only half the battle (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
Parent
Re: (Score:2)
Awesome to have you post this, Andrew. Actually I'm a bit embarrassed since I'm a typical ignorant slashdotter who only read the guardian summary article and not much of the paper itself--never expected to draw the attention of someone who actually knows what they are talking about, someone who was one of the original investigators!
In response to another poster who raised an eyebrow at my phrase "deja vu" I really meant that this article and experiment reminded me of the previous DNA experiment, which of c
One last math problem? (Score:2)
Wait. E.coli? As in a Escherichia The Killer Diarrhea Coli? Millions and millions and millions of reproducing E.coli bacteria? Not on my desk, thank you very much.
Re:One last math problem? (Score:4, Informative)
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.
Parent
quantum computer (Score:2)
Could a quantum computer be used to solve this?
Science Marches On (Score:2)
So now a dose of clap is better at math than the hooker that gave it to me. Or me, for that matter. Now I feel REALLY pathetic.
A use for keyboard crumbs after all (Score:2)
OK, so if I translate this correctly I may actually be typing on the most powerful part of my PC?
Thank God they didn't base this on swine flu - it's going at a rate as it is .. :-)
This is incredibly underwhelming (Score:3, Insightful)
Meh. (Score:2)
Hex, is that you? (Score:2)
Cool, but not useful (Score:2)
First, this is pretty cool. Enough said about that.
Unfortunately, I don't think this will be useful for solving NP-complete problems. For those of you who don't know much about algorithms, NP-complete problems are hard to solve because they become much harder as you make the problem "bigger". It is perfectly possible for problems to be solvable in a reasonable amount of time for small problem sizes, like n=3 that the authors of this article solved.
The paper explains that because bacteria can multiply exp
Re:this still does not prove p == np (Score:4, Interesting)
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.
Parent
Re: (Score:2)
Absolutely- the soap film computers are comparable to effective heuristic algorithms for the Steiner tree problem, but they come with no proof that their solution is optimal. And there are examples where they are demonstrably incorrect (suboptimal in total length) some fraction of the time. There are plenty of quick algorithms for problems if you drop the requirement to be correct all of the time!
Nevertheless, playing with soapfilms and pegs can be interesting and a good illustration of some of the subtle
Re: (Score:3, Funny)
"Moar protein plz!"
-- E. Coli