Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Bacterial Computer Solves Hamiltonian Path Problem

kdawson posted about 5 years ago | from the sicken-you-or-solve-your-problems dept.

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

cancel ×

135 comments

Sorry! There are no comments related to the filter you selected.

Summary is overrated (5, Informative)

FooAtWFU (699187) | about 5 years ago | (#28824505)

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 (1, Informative)

Anonymous Coward | about 5 years ago | (#28824529)

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:Summary is overrated (3, Funny)

Anonymous Coward | about 5 years ago | (#28824649)

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 (5, Funny)

rubycodez (864176) | about 5 years ago | (#28824755)

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

Re:Summary is overrated (3, Interesting)

kohaku (797652) | about 5 years ago | (#28825459)

Why is the GP modded over the parent? "Simply another NP-complete problem" and "not a special case" are just wrong. As can be found on wikipedia, [wikipedia.org] the following text states that solving one NP-complete problem faster means they are ALL solvable faster. Come on slashdot! Computational complexity 101!

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, with NP standing for nondeterministic polynomial time) is a class of problems having two properties

  • Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP.
  • If the problem can be solved quickly (in polynomial time), then so can every problem in NP.

Anyway, this article is about solving the problem in parallel with bacteria (which is totally cool, don't get me wrong.) It's not a faster algorithm, although I suppose you could argue that massively parallelizing it IS a faster solution.

Re:Summary is overrated (1)

Ethanol-fueled (1125189) | about 5 years ago | (#28824735)

Agreed, if they would have just used a garden-variety silicon computer and a variant of Dyke-stra's algorithm then they could have solved it with lesbians and not gone through the trouble of micromanipulation.

P.S. GTFO Slashdot religious fucks. Go get your cheap endorphin rush at your social masturbation tincan. The rest of us will think for ourselves, thank you. Your kind aren't welcome here.

Re:Summary is overrated (1)

thedrx (1139811) | about 5 years ago | (#28825641)

Your poststriptum is nicely put.

Re:Summary is overrated (1)

thedrx (1139811) | about 5 years ago | (#28825645)

*postscriptum

Re:Summary is overrated (1)

agg-1 (916902) | about 5 years ago | (#28826249)

Well, any problem in NPC is a "special case" of any other problem in NPC, up to polynomial reductions. That's what completeness means.

Re:Summary is overrated (1)

Mr.Bananas (851193) | about 5 years ago | (#28824695)

Yeah, in theory they could scale this to more cities with more bacteria, but they'd probably have to build something like Mother Brain to scale to thousands... and "silicon" of course can currently handle that just fine.

Fine achievement though, despite the summary's smug sensationalism.

Re:Summary is overrated (4, Insightful)

michelcolman (1208008) | about 5 years ago | (#28825241)

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.

Re:Summary is overrated (1)

juraj (262352) | about 5 years ago | (#28825563)

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 enumerate all combinations in DNA. Only for a few hundred cities, you get enormous mass of DNA (earth-like weights and more).

Re:Summary is overrated (1)

michelcolman (1208008) | about 5 years ago | (#28825787)

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

Re:Summary is overrated (1)

rafaelolg (1248814) | about 5 years ago | (#28826165)

Just use image analysis to find if there is any solutions. Something very simple like Gonzalez et al. [google.com.br]

Re:Summary is overrated (1)

SleepingWaterBear (1152169) | about 5 years ago | (#28826655)

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 have a awful lot less units to work with a a given size. Still in principle for problems that can be parallelized, having millions of 'processors' might be enough to make up for the size of the units you're working with.

Re:Summary is overrated (0)

Anonymous Coward | about 5 years ago | (#28826063)

It's a kdawson post. Throw in some exaggeration and something that sounds controversial and he'll post it in a jiffy without checking the facts, reading the article, and/or making sure that the links work.

Next up... (2, Funny)

sharp3 (1195261) | about 5 years ago | (#28824513)

Foot fungus solves graph coloring!

the possibilities! (4, Insightful)

Brian Gordon (987471) | about 5 years ago | (#28824533)

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.

Re:the possibilities! (2, Insightful)

Anonymous Coward | about 5 years ago | (#28824665)

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.

cue terminator joke in five, four, three... (2, Funny)

Anonymous Coward | about 5 years ago | (#28824679)

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

Re:cue terminator joke in five, four, three... (0)

Anonymous Coward | about 5 years ago | (#28824813)

BacNet strikes back.

Re:the possibilities! (0)

Anonymous Coward | about 5 years ago | (#28824683)

The advantage is, you don't need to run experiments over and over without repair. Humans are the best machines and they can't work without repair for ever. Humans are not scalable either. But still humans have best pattern recognition compared to any other work ever conceived.

Bottom line is to think different and to believe (like X-files)

Re:the possibilities! (0)

Anonymous Coward | about 5 years ago | (#28824775)

But... this way we can have REAL computer viruses! Like, you can infect people bacterial computer with an actual virus!
[yes I understand it doesn't exactly work like that.]

Re:the possibilities! (1)

maxwell demon (590494) | about 5 years ago | (#28825609)

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:the possibilities! (1)

tacarat (696339) | about 5 years ago | (#28825833)

Does that mean I'll be able to catch real STDs from bacteria internet porn one day?

Support Bacteria! (1)

naz404 (1282810) | about 5 years ago | (#28825501)

Support Bacteria! It's the only culture some people have!

Misleading (1, Insightful)

Anonymous Coward | about 5 years ago | (#28824555)

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.

old. (0, Troll)

Knoeki (1149769) | about 5 years ago | (#28824561)

I'm pretty sure I've seen this elsewhere yesterday.

So? (4, Insightful)

pushing-robot (1037830) | about 5 years ago | (#28824567)

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? (0)

Anonymous Coward | about 5 years ago | (#28824629)

Not really.

http://arxiv.org/abs/quant-ph/0502072

Re:So? (4, Informative)

rjh (40933) | about 5 years ago | (#28824867)

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

Re:So? (2, Insightful)

pushing-robot (1037830) | about 5 years ago | (#28825105)

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:So? (2, Interesting)

Bacon Bits (926911) | about 5 years ago | (#28825141)

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.

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 inherent in electron flow and the basic ability to electrically flip switches. Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.

Re:So? (1)

SlashWombat (1227578) | about 5 years ago | (#28825243)

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:So? (1)

cp.tar (871488) | about 5 years ago | (#28825499)

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 (1)

Sycraft-fu (314770) | about 5 years ago | (#28825379)

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 the ultimate devices for begin able to see how they "think" and for being able to reproduce results anywhere.

Now this is particularly useful because these are things humans are NOT good at. Computers compliment humans well.

Where they start to look inefficient, in a manner of thinking, is when you try to make them solve problems that aren't really in their domain. Things like "fuzzy logic" and so on. This isn't how they work, so it takes a lot of power to make them do it well. Good news is that because they are so fast, they've got lots of power to spare.

Now as for systems like this bacterial one, one of the problems is that though they get the answer, they don't know it is the right one. They get multiple answers, humans then have to go an look at them and figure out which one is right. That doesn't help much. This is not the case for a digital computer, when you have a program that does what it is supposed to do, it arrives at the result and it can tell you that is the correct result.

So unless a way is found to make these analog computers capable of analyzing their own results and getting the one correct answer, they are a novelty more than anything else. Most people don't have labs full of grad students to sift through the results.

Re:No, they are extremely efficient (1)

maxwell demon (590494) | about 5 years ago | (#28825635)

So unless a way is found to make these analog computers capable of analyzing their own results and getting the one correct answer, they are a novelty more than anything else. Most people don't have labs full of grad students to sift through the results.

You clearly didn't RTFA. The bacteria do analyze their own result: Those with the correct solution glow yellow.

Re:So? (1)

stephanruby (542433) | about 5 years ago | (#28825735)

May be they could replace our Slashdot editors instead?

we need a solution (-1, Troll)

Anonymous Coward | about 5 years ago | (#28824615)

we need something to kill fags. aids didn't do the trick well enough. we need all fags to die.

Evolution? (0)

Anonymous Coward | about 5 years ago | (#28824725)

The problem should take care of itself. It seems like they have a disadvantage in terms of natural selection...

Hmm (5, Funny)

parallel_prankster (1455313) | about 5 years ago | (#28824623)

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

Re:Hmm (2, Funny)

laejoh (648921) | about 5 years ago | (#28825535)

Thank $diety we're all slashdotters! The bacteria don't have to worry about skin being too narrow to contain.the truly marvellous proof!

Re:Hmm (1)

TempeTerra (83076) | about 5 years ago | (#28826049)

...I have discovered a truly marvellous proof of this, which this scrawny geek is too narrow to contain

Re:Hmm (1)

inamorty (1227366) | about 5 years ago | (#28826893)

Trust thrush.

Wonderful! (2, Funny)

Quothz (683368) | about 5 years ago | (#28824625)

So does this mean we're gonna have to re-educate the public and explain that they really can catch an infection from a computer virus? It wasn't that long ago that we were patiently explaining why that wasn't a concern.

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.

Re:Wonderful! (-1, Troll)

Anonymous Coward | about 5 years ago | (#28824643)

hahahaha

nigger.

A-choo! (4, Funny)

flatulus (260854) | about 5 years ago | (#28824641)

Aha!

Not a puzzle (0)

Anonymous Coward | about 5 years ago | (#28824647)

Correction: Hamiltonian Path is *NOT* a puzzle. With the problem statement, you can find the way to solve it very quickly. The only problem is, your best guess at how to solve it will take very very large time to find the solution (in general).

Puzzle is, when you have to think hard, how to solve it, no matter how long it takes.

-I don't want to be Anonymous, but "Creating an Account" at 100 different site sucks!

And we thought... (1)

Antony-Kyre (807195) | about 5 years ago | (#28824685)

licking keyboards [slashdot.org] were bad.

Ebola solves..... (5, Funny)

stox (131684) | about 5 years ago | (#28824687)

the population problem.

Re:Ebola solves..... (-1, Redundant)

Anonymous Coward | about 5 years ago | (#28825695)

Ebola solves the population problem.

But swine flu can solve this problem faster

Bacteria Driven Computers? - Slant (1)

Jack9 (11421) | about 5 years ago | (#28824703)

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.

comic con is for fags (-1, Troll)

Anonymous Coward | about 5 years ago | (#28824747)

die comic book faggots. comics are for low life assfags. go eat the shit out of another mans ass. die now!! god damn faggots.

From what I hear (1, Funny)

MLS100 (1073958) | about 5 years ago | (#28824767)

The hardware is really buggy.

*ducks*

geez. (1)

binaryseraph (955557) | about 5 years ago | (#28824785)

Talk about a computer virus. Norton Utilities now offering penicillin

But... (0, Redundant)

Brickwall (985910) | about 5 years ago | (#28824791)

.. does it run Linux?

this still does not prove p == np (1)

dawilcox (1409483) | about 5 years ago | (#28824799)

You slashdot editors need to look up a bit of what has already been solved.... Soap can solve the Steiner problem. Soap, in water, acts as a surfactant, which decreases the surface tension of the water. This acts to minimize the surface energy of the liquid. This should minimize surface area (graph weight), and solve the problem. However, there is a problem with saying that P == NP because of this. Reducibility is the issue. If you can't reduce all problems in NP to this, you're sunk. The article doesn't provide such a reduction. Until such a reduction is presented, I'll remain skeptical that these alternative formulations of the problem are really solving anything interesting.

Re:this still does not prove p == np (1, Insightful)

Anonymous Coward | about 5 years ago | (#28824869)

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 (3, Interesting)

rjh (40933) | about 5 years ago | (#28824879)

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:this still does not prove p == np (1)

call -151 (230520) | about 5 years ago | (#28826243)

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 subtleties of algorithms. I've seen decent examples in some museum exhibits [gjbgraphics.com] although usually their explanations are a little off, and I have a pair of plastic plates with some pegs that a student built for me for demonstrating, years ago, which has been a nice thing to have from time to time.

Damn it :( (0)

Anonymous Coward | about 5 years ago | (#28824831)

As if we didn't have enough problems with viruses already, and now they're introducing bacteria...

My Computer Died (3, Funny)

okmijnuhb (575581) | about 5 years ago | (#28824855)

Now when you say that your computer died, you may be speaking literally...

Good news for stinky nerds (2, Funny)

Myrcutio (1006333) | about 5 years ago | (#28824871)

So all that bacteria growing on those unhygienic D&D nerds is actually helping them with pathing, i knew they were cheating somehow, i could smell it...

It has always been the case (1)

juanergie (909157) | about 5 years ago | (#28824909)

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 and mightiest fighter airplane.

Computers are not problem solvers - they merely automate repetitive procedures or, at best, algorithmically apply a set of rules to a given problem -- Nature has always been more potent than computers.

I am impressed they can solve a simple problem with bacteria though. Maybe I should stop brushing my teeth and let the bacteria in my mouth say something intelligent.

Peace.

Re:It has always been the case (1)

Sir_Lewk (967686) | about 5 years ago | (#28825077)

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? (2, Funny)

noppy (1406485) | about 5 years ago | (#28824943)

Lets hype over it when it can run Linux

Re:Turing complete? (0)

Anonymous Coward | about 5 years ago | (#28825213)

Bacterium are the new Linux.

Re:Turing complete? (1)

troll8901 (1397145) | about 5 years ago | (#28825679)

Will Bacterix use GNOME, KDE, or another window manager?

Hamiltonian path != traveling salesman (3, Insightful)

Hitokiri Battousai (702935) | about 5 years ago | (#28824945)

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.

Re:Hamiltonian path != traveling salesman (0)

Anonymous Coward | about 5 years ago | (#28825393)

Well, given that Hamiltonian Path is NP-Hard and TSP is in NP, we can deduce that there is a polynomial-time algorithm for TSP using this machine in conjunction with a Turing machine.

Re:Hamiltonian path != traveling salesman (2, Informative)

dido (9125) | about 5 years ago | (#28825605)

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 convert the source problem instance you wanted to solve into the equivalent Hamilton path problem, and apply the reduction in reverse on the answers to get the answers you wanted for the problem you wanted to solve.

Biological computing not new (0)

Anonymous Coward | about 5 years ago | (#28824973)

Biology has been used on many occasions to solve computationally difficult problems, including cryptographic, NP, NP-Hard, and NP-Complete (Non-Deterministic Polynomial Complete). Fortunately, finding Slashdot on the internet only requires Dijkstras shortest path algorithm (a special bidirectional graph), with routers and routing tables as nodes (and great distances of fiber or cable as edges). Its neat to see how really low-level computational elements like bacteria can be used in a massively parallel way to solve these problems though.

parallel computations only half the battle (3, Insightful)

caseih (160668) | about 5 years ago | (#28825035)

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 (5, Interesting)

Atmchicago (555403) | about 5 years ago | (#28825521)

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:parallel computations only half the battle (1, Insightful)

Anonymous Coward | about 5 years ago | (#28826181)

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).. ??

Re:parallel computations only half the battle (1)

juraj (262352) | about 5 years ago | (#28825583)

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:parallel computations only half the battle (1)

Scythal (1488949) | about 5 years ago | (#28825639)

Deja vu?
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. As they say, DNA sequencing could be acceptable given the low rate of false positives, you need to do it to read the solution anyway (but yes... at what cost?).

I for one... (0, Redundant)

cigawoot (1242378) | about 5 years ago | (#28825059)

I for one welcome our new Bacterial Overlords.

Re:I for one... (1)

maxwell demon (590494) | about 5 years ago | (#28825665)

Yes, but do they run Linux?

Wow (0)

Anonymous Coward | about 5 years ago | (#28825071)

This project started at Missouri Western State University. I'm a computer science student there. It's strange seeing some of my friends names linked to a ./ article. The project started as part of the University's "summer research" program. Where undergrads get to do some really cool research projects. I joined the economics team that made a crappy NWN mod to teach principles of economics. Great choice that was... they took their project to a competition called iGem and now their names are in a peer reviewed journal.

Press Release? (0)

Anonymous Coward | about 5 years ago | (#28825079)

Any word from the bacteria yet?

Re:Press Release? (2, Funny)

shentino (1139071) | about 5 years ago | (#28825473)

"Moar protein plz!"

-- E. Coli

Lewis Hamiltonian path? (0)

Anonymous Coward | about 5 years ago | (#28825081)

Does this mean Lewis Hamilton is going to start winning F1 races again, now they've solved the problem of which route he should take?

Bacteria doing math? (1)

Quantos (1327889) | about 5 years ago | (#28825165)

Are they getting that hard up for grants? What is it, flagellate for a one, don't flagellate for a zero? Everybody get in line so we can read the binary?

One last math problem? (1)

hwyhobo (1420503) | about 5 years ago | (#28825235)

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? (1)

maxwell demon (590494) | about 5 years ago | (#28825541)

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? (3, Informative)

asdf7890 (1518587) | about 5 years ago | (#28825657)

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.

Genetic systems (0)

Anonymous Coward | about 5 years ago | (#28825249)

bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems

With actual genes, no less.

quantum computer (1)

shentino (1139071) | about 5 years ago | (#28825437)

Could a quantum computer be used to solve this?

Re:quantum computer (1)

maxwell demon (590494) | about 5 years ago | (#28825681)

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:quantum computer (1, Interesting)

Anonymous Coward | about 5 years ago | (#28825901)

Not in polynomial time.
It is conjectured that quantum computers can't solve NP-complete problems in polynomial time.

Count the mass of DNA! (1)

juraj (262352) | about 5 years ago | (#28825571)

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 genetic manipulation excercise, I like that they contribute to the "standard biological components database", but it has no implication for computational complexity.

And it won't solve complex problems better than sillicon, because instead of time, you need mass. There's simply not enough material and space on this small planet for DNA solution of hamiltonian path for >500 cities.

I Thought... (1)

d'baba (1134261) | about 5 years ago | (#28825689)

Willy Loman solved this problem years ago.
---
Free The Mouse

Science Marches On (1)

hyades1 (1149581) | about 5 years ago | (#28825711)

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 (1)

cheros (223479) | about 5 years ago | (#28825797)

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? (1)

EmagGeek (574360) | about 5 years ago | (#28825839)

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 (2, Insightful)

xZgf6xHx2uhoAj9D (1160707) | about 5 years ago | (#28826157)

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.

Meh. (1)

tenco (773732) | about 5 years ago | (#28826301)

And i thought this had something to do with the Hamiltonian Principle. Turns out it's only CS.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>