Bacterial Computer Solves Hamiltonian Path Problem 135
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."
Summary is overrated (Score:5, Informative)
Re: (Score:1, Informative)
Also, the Hamiltonian path problem is not a special case of the traveling salesman problem, it is simply another NP-complete problem that is quite similar to the traveling salesman problem.
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.
Re: (Score:3, Funny)
First bacterial computer virus? (Score:2)
Re: (Score:2)
not even my I.T. friends post on slashdot, must take an exception level of lameness to participate here
Re: (Score:3, Interesting)
Re: (Score:1)
Re: (Score:2)
Will it have fucking Buddanaise to fucking dip it into?
Re: (Score:1)
Re: (Score:2)
Re: (Score:1)
Re: (Score:1)
Re: (Score:1)
Fine achievement though, despite the summary's smug sensationalism.
Re:Summary is overrated (Score:4, Insightful)
Re: (Score:1)
There are lots of interesting algorithms, that are probabilistic. The definition is, that if you run it long enough, the solution will be found.
Reliability is also backed up by the times you run experiment. You can easily discard pink colours, if you get yellow, you can check the result (remember, it's NP, so checking, if the answer is okay is deterministic polynomial, i. e. fast). So filtering out the wrong solutions is not a problem.
The principial problem is, that it does not scale well. You need to enume
Re: (Score:1)
There are lots of interesting algorithms, that are probabilistic. The definition is, that if you run it long enough, the solution will be found.
Indeed, and such algorithms are widely used in practice, but they are not theoretically considered a "solution" because you might (in theory) have to wait forever to get a path, and you will never really be sure that no path exists (which is an important element of the Hamiltonian Path Problem). If a probabilistic algorithm is considered to be good enough, they should at least compare the bacteria against a computer running a probabilistic algorithm as well, and find that the computer is probably a lot fas
Re: (Score:1)
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:1)
Re: (Score:2)
Re: (Score:2)
The problem is, even the least green computer solving the problem wouldn't be characterized as an ecological disaster. Choose the bacteria carefully!
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:1)
WTF - traveling salesman with three points, one of which is the start and one of which is the end - what paths are there to choose from?
Re: (Score:1)
--
There are 10 types of people in the world: those who understand binary, and those who don't.
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.)
Support Bacteria! (Score:1)
Re: (Score:1)
Well, given that a virus injects new DNA, it just may work like that. Imagine a virus which uses only a fraction of the infected bacteria for reproduction, but modifies the DNA in the others to alter the computation (in the case in question, a simple example would be to make the bacteria glow yellow unconditionally). Or maybe a virus which selectively kills bacteria with a certain DNA configuration.
Re: (Score:1)
Misleading (Score:1, Insightful)
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? (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)
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:1)
You clearly didn't RTFA. The bacteria do analyze their own result: Those with the correct solution glow yellow.
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
Re: (Score:1)
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.
Re: (Score:2)
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.
From what I hear (Score:1, Funny)
The hardware is really buggy.
*ducks*
geez. (Score:1)
But... (Score:1, Redundant)
this still does not prove p == np (Score:1)
Re: (Score:1, Insightful)
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.
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.
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
My Computer Died (Score:4, Funny)
Good news for stinky nerds (Score:3, Funny)
Re: (Score:2)
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
Re: (Score:1)
Will Bacterix use GNOME, KDE, or another window manager?
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
Re: (Score:2)
I didn't RTFA, and the other comments in the discussion make me skeptical anyway, but your post seems to contradict itself. If the Traveling Salesman Problem is NP-complete (which I know to be true) and the Hamiltonian Path Problem is also NP-complete (which I assume is true from this discussion), then solving one problem is isomorphic to solving the other and a solution to either can be transformed into a solution to the other in polynomial time. If you'd be impressed "if they found the shortest path on
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
Re: (Score:1, Insightful)
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
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
Re: (Score:1)
As I wrote, it still does not solve the mass of DNA required to enumerate all solution. It should be however noted, that a good solution of this particular problem is important, because as it's NP-complete, all other NP problems could be solved with cca the same complexity.
So this is a good problem, because it can be easily represented in DNA sequences and if solved, any NP algorithm could be solved using the machine solving this problem.
Re: (Score:1)
Not quite, they cite his paper in the references and acknowledge Adleman's work as "seminal" (pp. 4-5). But where he used PCR to replicate DNA fragments (where nucleotides coded for data of the mathematical problem instead of actual amino acids), they use a living organism - the E. coli bacteria.
The problem they claim to solve is the Hamiltonian path problem, so I'm not sure what you mean by "identify the shortest one". But clearly they left the problem of false positives out for a later study.
Bacteria doing math? (Score:1)
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: (Score:1)
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.
I've got bad news for you: You already have millions and millions and millions of reproducing E.coli bacteria in your colon.
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.
Re: (Score:2)
So... no food allowed in the computer center. :(
quantum computer (Score:2)
Could a quantum computer be used to solve this?
Re: (Score:1)
Since a quantum computer can solve everything a classical computer can, of course a quantum computer can solve it (provided you manage to build one, of course).
However, the real question is: Can a quantum computer be used to solve it efficiently? Well, it's generally assumed that quantum computers cannot efficiently solve NP-complete problems (there's no proof, but then there's no proof for classical computers either).
Re: (Score:1, Interesting)
Not in polynomial time.
It is conjectured that quantum computers can't solve NP-complete problems in polynomial time.
Count the mass of DNA! (Score:1)
This is not that important as it sounds. It would not be able to solve NP-complete problems for large inputs, because it enumerates all possibilities in DNA base-pair combinations. This has actually been done before with pure DNA and their manipulation (now they use bacteria for color-marking and thus selection of the right solution's DNA sequence).
Anyways, this does not scale well, having only a few hundred cities would require DNA, that would weight cca the mass of our earth.
So this result is nice as a ge
I Thought... (Score:1)
---
Free The Mouse
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 .. :-)
Where is PETA on this? (Score:1)
PETA already objects to using bacteria to clean up oil spills... what do they think about using bacteria to do math?
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
My gut tells me... (Score:1)
Can a bacterial computer ... (Score:2)
... be used to download p0rn? Just asking.
On second thought ..... Eeewwww!! That would be pretty nasty looking p0rn.
One thing is that your computer can infect you (Score:1)
The Irony of It All (Score:1)
Keyboards are supposed to have more bacteria than a toilet seat. That means every time I start typing a program I have destroyed the solution to one of life's great problems. My keyboard solves problems I couldn't possibly program solutions too!!
I guess I should just retire and each day take a picture of my keyboard to save the current solution to a problem, then piss on it to erase the current solution and start the new program running. I guess if it is not to complex a problem, I can take a picture of my
Life, the Universe, and Everything? (Score:2)
Am I the only one who thought of Douglass Adams' Life, The Universe, and Everything [wikipedia.org] when reading this article?
For those few of you wondering what I'm talking about, this is one of the books in the Hitchhiker's Guide to the Galaxy series, and in it, it is revealed to us that the entire planet earth and all life on it was constructed as a large biological computer to find the right question which would make sense of the answer (which we're already given: 42) to the question of Life, the Universe, and Everythi
Re: (Score:3, Funny)
"Moar protein plz!"
-- E. Coli
Re: (Score:1)
Yes, but do they run Linux?