DNA Solves Million-Answer NP-Complete Problem

cybrpnk writes: "A 'DNA computer' has been used for the first time to find the only correct answer from over a million possible solutions to a computational problem. Leonard Adleman of the University of Southern California in the US and colleagues used different strands of DNA to represent the 20 variables in their problem, which could be the most complex task ever solved without a conventional computer. Details to be published in Science."

Comments

Press release here...

[56ker]

Where is the promised press release here?

is this breakthrough a threat to security?

[ardiri]

now, one needs to ask - "can this same technology be used to break codes/algorithms used within security?" the article is a bit lacking in details of how they achieved this exactly, but, koas theory is in action here.

Re:is this breakthrough a threat to security?

[r00tarded]

well is guess Leonard Adleman is the guy to know.
he would be the 'A' in RSA.

Re:is this breakthrough a threat to security?

[Anonymous Coward]

I hate to do this, but as someone who has studied CHAOS theory, random comments like this irk me...

"lacking in details, but koas thoery is in action"

Little bit of chaos theory:
When thinking about chaos, really focus on the most important criterion: sensitive dependence on initial conditions.

What that means is that a system is chaotic if:
no matter how small of a change you make to the initial system, within a small amount of time the behavior will be WILDLY different.

Soooo... What does chaos theory have to do with ANYTHING here? I mean, pretty much EVERYTHING we encounter in every day life is chaotic at some scale, and the interactions of DNA are likely similar. But this has nothing to do with its computational ability.

Extreme speculation: EXCEPT perhaps chaos's tendency to keep the system out of periodic states (where it repeats itself over and over again) allows it to explore all possible combinations better.

Re:is this breakthrough a threat to security?

[kyras]

In theory, sure, you can attack encryption that's based on the difficulty of factoring. The researchers used the DNA computer to solve a 3-SAT instance. You can reduce factorization to a SAT instance pretty easily; I've actually written code to do this before. It basically works like this:

1. Take a multiplier circuit with 2n bits of output (where 2n is slightly greater than the size of the product of primes you're trying to factor, eg, in RSA).
2. Turn the circuit into a CIRCUIT-SAT instance (nontrivial, but doable, I have code that does it for 2 types of multiplier circuits, array and Wallace tree). The SAT variables are the input bits of the multiplier.
3. Add a couple of clauses to guarantee that neither of the inputs can be "000...001", i.e., that you won't end up factoring the 2n bit product-of-primes as 1 and itself. This is not strictly necessary if the product of primes doesn't fit in n bits, I don't think.
4. Reduce to 3-SAT.
5. Feed to DNA computer.
6. Wait.

The thing to note here is that even though the researchers solved a nontrivial 3-SAT instance (i.e., it had only one solution, like a factorization problem involving the product of 2 primes), it was still relatively small scale. You can't really solve the problem "on paper", but your computer can do it with a good SAT solver like CHAFF in a reasonable amount of time (i.e., much less than the life of the universe). Tough factorization problems involve many more clauses and variables, so I don't think this is a threat to the security of your 2048-bit RSA key just yet.

questions, questions

[56ker]

But with only a million different combinations - surely this is no match for today's computers yet! How long will it be before it can be used for more practical problems?

Re:questions, questions

[sketerpot]

This is an important breakthrough. They have shown that DNA can solve their test problem, and that is a big and necessary step on the way to creating DNA computers more powerful than comventional computers for some special problems.

I look forward to when this will find a practical use. It is certainly possible. Hopefully this experiment generates some interest, not to mention good ideas for future DNA computers.

Which problem?

[cperciva]

The article is a bit garbled (exponential time != NP-complete!) so it's a bit hard to work out what problem they were looking at.

I'm guessing 2-SAT; can anyone confirm/deny this?

Re:Which problem?

[Rudie]

But 2-SAT is not in NP-complete nor needs exponential time. Maybe you're thinking of 3-SAT or just plain SAT?

Re:Which problem?

[Permission Denied]

2-SAT is in P. 3-SAT, 4-SAT and so on are all NPC. In fact, 3-SAT was the first problem which was proved to be NPC (and, AFAIK, the only problem proved to be in NPC without using a Karp reduction proof).

Re:Which problem?

[allanj]

If memory serves me correctly, the problem described in the REAL article is a 3-SAT, but algorithmics class was years back and beginning to fade from memory...

Re:Which problem?

[cperciva]

Oops. It's been a while since I took those courses...

Re:Which problem?

[Permission Denied]

Yep, the article describes 3-SAT - so you're remembering your algorithms class just fine. Also, the article linked from the slashdot story describes 3-SAT in a nice, easy-to-understand but not too dumbed-down way (I posted before reading the article). I just looked it up and 3-SAT was proved to be NPC in 1974 by Cook and Levin.

Re:Which problem?

[johndv]

The first problem proved to be NP-complete is SAT (that's Cook Theorem). 3-SAT is the first problem proved NP-complete by Karp in his seminal paper.

Re:Which problem?

[Permission Denied]

Mea culpa, you're right. It's kind of embarassing that my comment was modded up for all to see and I was inexcusably WRONG.

Re:Which problem?

[Lictor]

It was definitely 3-SAT; I just spoke with one of the experimenters yesterday.

Re:Which problem?

[Anonymous Coward]

It's dumbasses like you that give slashdot a bad name.

Re:Which problem?

[Anonymous Coward]

It was definitely 3-SAT; I just spoke with one of the experimenters yesterday.

Well tell them than a 24-clause 20-variable 3-SAT problem isn't very hard. You can number the variables in an arbitrary way, sort the clauses by "smallest index variable it uses" and start assigning values from the end. You only need very little guesswork.(Yeah, I'm contesting the claim that "A DNA-based computer has solved a logic problem that no person could complete by hand")

You need about 5.1909 times more clauses than there are variables to get a "tough" 3-SAT instance. That means 104 clauses, not 24.

Re:Which problem?

[ToLu the Happy Furby]

I just looked it up and 3-SAT was proved to be NPC in 1974 by Cook and Levin.

The first problem proved NPC was general CNF SATISFIABILITY, by Cook in 1971. SATISFIABILITY can be shown to polynomially reduce to (CNF) 3-SAT (proving that 3-SAT is NPC), and 3-SAT reduces to lots of other problems, which themselves reduce to even more problems (this is the typical way to prove a new problem NPC).

I somewhat doubt that 3-SAT wasn't proven NPC until 1974, because SAT->3-SAT is a pretty easy reduction. (You just introduce a bunch of dummy variables, e.g. (a or b or c or d) becomes ((a or b or z) and (~z or c or d)) and so on; the reduction is linear time in the number of variables in the original expression.)

Re:Which problem?

[Lictor]

>Well tell them than a 24-clause 20-variable 3-SAT problem isn't very hard.

I don't think anyone would argue with you on this point. These are still toy examples... proof-of-principle type stuff. Remember that this result came out of Len Adleman's lab; If you're aware of who Adleman is, then I assume you'll agree its likely he was quite aware of this fact. If you don't know who Adleman is... well, I assume anyone mathematically literate enough to come up with the (quite correct) argument that you made would have to be at least passingly familiar with him.

If you're interested in attacks on DNA computing, I highly recommend reading:

Juris Hartmanis. On the weight of computations. Bulletin of the European Association For Theoretical Computer Science, 55:136--138, 1995.

Its short, but sweet.

As for the "no person could complete by hand" bit; I have to agree with you. The concept of "doable by hand" is pretty ill-defined. In any case, thats not the *real* point of the paper. The point is that the lab tech who implemented the computation did not know the solution a priori. Seems like a pretty obvious control, but so far all previous experiments have been so trivial that a human (or moderately skilled monkey) could trivially see the answer just by looking at them.

Re:Which problem?

[kyras]

It was 3-SAT. 2-SAT is not in NP. See the (fantastic) algorithms book by Cormen, Leiserson and Rivest for proofs. IIRC any SAT problem can be reduced to 3-SAT.

Nice, but...

[Anonymous Coward]

this doesn't make NP-complete problems polynomial ofcourse.

Still, impressive!

Re:Nice, but...

[s20451]

Indeed. The advantage of DNA computing is massive parallelism, but consider the 3-Satisfiability problem (the classic NP-complete problem) with n predicates. Regardless of the number of parallel processors (be they silicon or DNA), the only known algorithm has complexity O(2^n), which means:

• For n=10, a few thousand operations are required.
• For n=30, a few billion operations are required.
• For n=250, somewhere around 1e+80 operations are required, which is roughly the same number as the number of atoms in the universe.

So imagine a DNA computer consisting of every atom in the universe -- even for this computer, a solution to 3-Satisfiability for n>250 would be basically hopeless.

Re:Nice, but...

[gkatsi]

These numbers are nice, but ignore the fact that the current algorithms for solving SAT can routinely solve random 250-variable problems in subsecond times and even larger structured problems. zChaff, the fastest solver currently has even solved some 1-million variable problems (of course it probably took a few days, but it's still better than the multiple-universe-lifetimes prediction of 2^n).

Re:Nice, but...

[Anonymous Coward]

almost there, but the machine consisting of every atom in the universe would do that in a few clockcycles. (which is probably around 10^-30 s or so)
if it was capable of utilizing all of its atoms for such a short time that is. more realistic vision would be to use a smaller portion of it and for a longer time. (say, 1000 ly space for 1000 years)

Re:Nice, but...

[Rudie]

Yes, but it turns out that not all instances of 3-SAT (or SAT) actually require that much time. Do a search on Google for "phase transitions in SAT" for more information.

This is the future...

[Sunda666]

Our old binary digit computers have been around for AGES (50+ years in tech time ;-)

It is really the time for searching new and more complex computer architechtures if we ever want to have true IA (a la HAL 9000). I always wondered why ppl insist on building neural nets based on ordinary computers rather than building them on dedicated neural hardware (expeeeensive, but needs to be tried more often).

Of course, today's computers do a good job resolving them, but there are too many architechtural limitations. Brains are a hella lot older than computers, and a hella lot more advanced (but very fragile).

Way to go dudes.

Re:This is the future...

[tomstdenis]

This isn't new research. In fact Adleman has published materials on his results before.

The big setbacks of DNA computing are

1. Slow to setup
2. Takes a while to get results
3. Has a high rate of error [compared to a typical computer]

What people mistake is that while a DNA computer could test 2^n cases simultaneously it still takes a while to get the results back. During that time errors can creep in (this is real life...)

Tom

Real article

[mnordstr]

Here is the article at USC which covers the subject, including an interesting picture!

Re:Real article

[bcrowell]

And here's the group's web page, including their preprints and FAQ. No preprint of the present paper, though.

Haiku

[Anonymous Coward]

Digital is old;
Genetic algorithms
Are quite new, again.

Here's a Thought

[Anonymous Coward]

Can't we somehow sue Microsoft with this new knowledge?

And in 5 years Microsoft will say...

[Ozan]

...it's not a bug it's a mutation.

Re:And in 5 years Microsoft will say...

[Anonymous Coward]

How the hell does this get modded up this high? What is the relevance?

Re:And in 5 years Microsoft will say...

[Anonymous Coward]

It got modded up because it's making a joke at Microsoft's expense. And, as we all know, to slag opff Microsoft is a sure-fire way to get modded up.

Re:And in 5 years Microsoft will say...

[Anonymous Coward]

If you were a registered user, you could set your comment options to downgrade "Funny" comments to 0 so you wouldn't see them.

Re:And in 5 years Microsoft will say...

[Anonymous Coward]

Fucking Micro$oft fucking suck rocks. Their shitty software crashes all the time and costs a pissing fortune.

Re:And in 5 years Microsoft will say...

[KlausBreuer]

...just after they trademark the abbreviation 'DNA'...

Re:And in 5 years Microsoft will say...

[Anonymous Coward]

And I encourage him to. Anyone who gets angry at a funny should be beaten.

And anyone who mods down funny gets beaten with a metamod stick.

Which OS?

[Gangis]

Which OS did they use? Microsoft DNA?

*rimshot*

Travelling Salesman

[Rudie]

After reading the article at USC it seems to me that they have solved an instance of the Travelling Salsesman Problem of size 20 encoded in SAT, can anyone confirm or deny this?

Very interesting in any case, well done.

Re:Travelling Salesman

[Anonymous Coward]

Adleman and co-workers expressed their problem as a string of 24 'clauses', each of which specified a certain combination of 'true' and 'false' for three of the 20 variables.

looks like 3SAT to me.

Re:Trolls Must Go.

[Anonymous Coward]

Relevant and meaningful. Two words that are all too often lost in the heightened "signal to noise" ratio that trolls are forcing on the intelligent readers and posters of Slashdot.

A heightened signal to noise ratio is generally considered a good thing.

I'm no genius.

Quite so.

I must resist....

[Rhinobird]

I must resist my urge for an inane beowulf cluster comment here....so instead...can you imagine a beowulf cloned with one of these?

Re:I must resist....

[Mr Teddy Bear]

Actually, the beowulf comment MIGHT actually be applicable this time. Because that is what clustering is all about. So really... a beowulf cluster of digital machines is an attempt at making one huge DNA machine.

Now if only they could stop making the damn DNA computer morph into Bill Gates. And I thought sheep were baaaad.

Re:I must resist....

[Rhinobird]

please forgive me, for i know not what i do...plus i'm really sleepy...

Re:I must resist....

[sketerpot]

If you won't make an inane beowulf comment, I will.
Imagine a beowulf cluster of these!
It's easy to imagine, since that is basically what DNA computers are: clusters of DNA molecules.

They can put a lot of DNA molecules together and have them compute in parallel, which is why this has so much potential.

Re:I must resist....

[Cowculator]

A Beowulf cluster of DNA?

I think it's called the human body...

before it get's slashdotted

[Anonymous Coward]

'DNA computer' cracks code
15 March 2002

A 'DNA computer' has been used for the first time to find the only correct answer from over a million possible solutions to a computational problem. Leonard Adleman of the University of Southern California in the US and colleagues used different strands of DNA to represent the 20 variables in their problem, which could be the most complex task ever solved without a conventional computer. The researchers believe that the complexity of the structure of biological molecules could allow DNA computers to outperform their electronic counterparts in future (R Braich et al 2002 Science to appear).

Scientists have previously used DNA computers to crack computational problems with up to nine variables, which involves selecting the correct answer from 512 possible solutions. But now Adleman's team has shown that a similar technique can solve a problem with 20 variables, which has 220 - or 1 048 576 - possible solutions.

Adleman and colleagues chose an 'exponential time' problem, in which each extra variable doubles the amount of computation needed. This is known as an NP-complete problem, and is notoriously difficult to solve for a large number of variables. Other NP-complete problems include the 'travelling salesman' problem - in which a salesman has to find the shortest route between a number of cities - and the calculation of interactions between many atoms or molecules.

Adleman and co-workers expressed their problem as a string of 24 'clauses', each of which specified a certain combination of 'true' and 'false' for three of the 20 variables. The team then assigned two short strands of specially encoded DNA to all 20 variables, representing 'true' and 'false' for each one.

In the experiment, each of the 24 clauses is represented by a gel-filled glass cell. The strands of DNA corresponding to the variables - and their 'true' or 'false' state - in each clause were then placed in the cells.

Each of the possible 1 048 576 solutions were then represented by much longer strands of specially encoded DNA, which Adleman's team added to the first cell. If a long strand had a 'subsequence' that complemented all three short strands, it bound to them. But otherwise it passed through the cell.

To move on to the second clause of the formula, a fresh set of long strands was sent into the second cell, which trapped any long strand with a 'subsequence' complementary to all three of its short strands. This process was repeated until a complete set of long strands had been added to all 24 cells, corresponding to the 24 clauses. The long strands captured in the cells were collected at the end of the experiment, and these represented the solution to the problem.

According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s. They are optimistic that such 'molecular computing' could ultimately allow scientists to control biological and chemical systems in the way that electronic computers control mechanical and electrical systems now.

Author
Katie Pennicott is Editor of PhysicsWeb

Re:I AM NOT A TROLL!

[Anonymous Coward]

ahhh shaddup ya troll!

Slashdot doesn't care

[Anonymous Coward]

If you really wanted to be troll-free, you'd read at +2.

However, the reason there are trolls is because slashdot doesn't give a rat's ass about the reader base. They have bugs they won't fix, and CmdrTaco won't even go back to school for grammar lessons. Then there is the moderation scandal they're involved in. The list goes on and on.

And they wonder why no one will give them money for subscriptions to slashcrap.

Sod off.

for comparison sake

[Alien54]

It would be interesting to find out what the comparitive time for finding an answer would be for common conventional computers. vs this process.

at least we would have a benchmark of sorts.

I imagine that the problems of creating a truly AI computer will be solved using a DNA based computer.

;-)

Re:for comparison sake

[dollargonzo]

that is the biggest illusion people have themselves running under. everyone seems to think the only problem with as you call it "truly AI computer", which doesnt even make much sense in itself, but ill give u the benefit of the doubt...

is computing power and parallel processing vs the inherently serial nature of todays conventional computing solutions. the benchmark idea is nice, but the BIGGEST problem with AI is trying to create a model that can handle every kind of input (and even one to start with would be nice) and be able to generalize concepts as well as learn independantly (without predefined associations between internal structure and external input).

computing power is nice, but we can't even create the correct models yet. even if its slow, at least it'll work. sure, DNA sounds nice...cause its biological ala humans, but beyond that, its just another computing method.

QED

Re:for comparison sake

[gkatsi]

On, say, a P3 1Ghz.... I guess it would talk around 0.000000 sec, if you use some of the older algorithms. That is, times() is not accurate enough to measure how long it would take.

That would be even faster for newer and better algorithms.

Need to know all the answers?

[glasslemur]

Each of the possible 1 048 576 solutions were then represented by much longer strands of specially encoded DNA, which Adleman's team added to the first cell

So they had to go through and find all the possible answers and put them in the mix? I don't think this will every be a viable solution when to find the correct answer you have to know all the wrong ones as well. Part of problem solving is starting out with 0 answers. I bet they couldn't use the DNA computer to figure out all those 1048576 wrong solutions. Although I think it would be an interesting concept, until they can figure out a way to solve problems without knowing all the answers, I do not see how it could be used for serious calculations. I think it could possibly be the next great search engine, or maybe an RC5 engine. But how long would it take to encode 18,446,744,073,709,551,616 strands of DNA?

Re:Need to know all the answers?

[tomstdenis]

Actually the correct answer should stand out like a beacon.

In early Adleman experiments the correct solution is one where the opposing strands completely bind together. Then they use a comb+gel+electrode+glow_in_dark_radioactive_die. The shorter strands will make it further through the gel towards the electrodes. the longer [complete answer] strand will not move far.

Obviously new DNA computers use different filtering techniques...

Another thing you should read up on is PCR or Polymeraese Chain Reaction [and I know I can't spell]. Its a technique that won a Nobel prize. I don't recall the technique but it involves making each strand duplicate themselves. So to get the 2^64 strands you alluded to you apply the PCR technique 64 times.

[no mention of errors...]

Tom

Re:Need to know all the answers?

[Anonymous Coward]

Er, they simply get all possible solutions to a problem first. For instance, in a factorisation problem, we know that certain numbers are not possible solutions (ex:- even numbers), so they use some sort of preliminary criteria to get a possible solutions.

Re:Need to know all the answers?

[glasslemur]

PCR would really not apply because as you said 'it involves make each strand duplicate themselves'. So if you have 2^64 duplicate strands you would have 2^64 copies of 1 answer. You would need to create 2^64 unique strands to get that many answers.

Re:Need to know all the answers?

[tomstdenis]

To best honest I don't know how to answer. Its been 2 years since I touched on this [it was a high school independent study]. I know they use PCR in the prep. work of the test.

There is something missing from the picture...

Tom

Cool, but...

[allanj]

The REAL article states that

"It would take a breakthrough in the technology of working with large biomolecules like DNA for molecular computers to beat their electronic counterparts".
So while the article also mentions code-breaking as an obvious application for this ... device ..., electrons will be our computing friends for the foreseeable future.

LSD

[GigsVT]

And to think, LSD made this all possible

"Would I have invented PCR if I hadn't taken LSD? I seriously doubt it,"

-- Dr Kary Mullis, Nobel Prize Winning inventor of the Polymerase Chain Reaction that allows pretty much all the modern research in DNA technology.

And to think on the same Google search that I found that, there was a sponsered link to "How drugs support terrorism" from the government.

Re:LSD

[Anonymous Coward]

This is nothing but the opinion of one person, and even he won't stand behind it with 100% conviction. Unless you can prove 100% that LSD 'enlightened' him to create PCR, you have nothing to stand on.

Re:LSD

[Anonymous Coward]

You sound like a very boring person.

Re:LSD

[Xenographic]

Ergo, cloning supports terrorism; specifically bioterrorism. Just imagine how terrified you'd be if someone cloned Britney Spears... :)

Re:LSD

[cduffy]

This is nothing but the opinion of one person, and even he won't stand behind it with 100% conviction. Unless you can prove 100% that LSD 'enlightened' him to create PCR, you have nothing to stand on.

Being the one person who is qualified to discuss the creation of PCR, I think his opinion carries some weight. Further, 98% (or 75%, 50% or even 15%) opinions are certainly not "nothing" -- I don't have to be 100% sure that leaving the gas on without a lit pilot will start a fire to take action on it; similarly, I'll gladly use birth control even if it isn't 100% effective, and if I have a chance to play some game that will give me a 10x return 15% of the time, I'm in.

Requiring 100% certainty as to the possible benefits of any transaction is a sure way to prevent oneself from even considering what may (or may not) be a worthy endevour.

Re:LSD

[areiosoltani]

well, that ass nugget didn't invent PCR all by himself--he took his Cal colleague Norm Arnheim's discovery of temperature cycling of DNA polymerase and then stuck in a thermostable enzyme derived from Thermus aquaticus or more commonly Taq, then promptly screwed the other guy out of the patent and the nobel prize. kary is a jerk.

Is this new?

[tomstdenis]

Two years ago I bought

ISBN 3-540-64196-3

which discussed Adlemans experiements.

How could this article describe it as the "first" dna computer used to solve a problem?

Re:Is this new?

[Lictor]

Well it certianly isn't the "first" DNA computer to solve a problem. However, it *is* the first one to solve a problem that would be seriously non-trivial for a human to do by hand.

Re:Is this new?

[mofolotopo]

Precisely my question. I would swear that I saw an article about this exact experiment using eight variables in SciAm three or four years ago. My first reaction when I saw this piece on Slashdot was actually "this is news?".

Re:Is this new?

[tomstdenis]

Ah, ok I misread that. You're right the essence of the article is that the problem was more complex.

Tom

Re:Not computing

[Anonymous Coward]

I thought that a process isn't really computing unless it's done with a read/write head on an infinitely long paper tape.

Grow an imagination, dude. Or buy a book on the theory of computation (Sipser wrote a very good one).

Great

[Chayce]

Now how many months before they come out with a USB version?

It's only a matter of time...

[guttentag]

before we hear:

It looks like you're attempting mitosis. Now would be a great time to sign up for a Passport account. WARNING: Are you sure you want to attempt mitosis without a Passport account? Your ancestors may regret it!

And on the other side of the coin, the Open Source DNA advocates will be saying:
You don't need a Passport account to have kids, honey. Yes, it's perfectly safe. Support? Who the hell told you Microsoft was going to support our child?! A free PC?!

Re:It's only a matter of time...

[Ionizor]

Your ancestors may regret it!

Your ancestors? I'm guessing you mean descendants. I really doubt my dead great-grandfather cares about mitosis.

Re:It's only a matter of time...

[guttentag]

I thought about that after I hit submit -- it was late... but actually, if your ancestors (which would presumably include your modern predecessors... parents, grandparents, etc.) believed in natural selection they have an interest in your mitosis.

Re:It's only a matter of time...

[Peter Harris]

Err, isn't that meiosis? Or are you an amoeba?

Re:It's only a matter of time...

[YU Nicks NE Way]

Actually, I think that it's nuclear fusion, not meiosis. In humans, only males have any cells whatsoever which undergo meiosis in adulthood.

Re:Not computing

[Anonymous Coward]

(replying to myself)
Also, note that Leonard Adleman (the researcher behind this DNA research) is one of the inventors of RSA encryption. You really sound like an asshole when you say that he doesn't know anything about real computation.

Re:Not computing

[Anonymous Coward]

YHBT. YHL. HAND.

don't hold your breath

[hyrdra]

According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s. They are optimistic that such 'molecular computing' could ultimately allow scientists to control biological and chemical systems in the way that electronic computers control mechanical and electrical systems now.

Huh? What they did here is use the self-construction property of DNA whereby only the respective nucleotides A, T, C, and G only form a bond with their compliment.

That means you can have millions of solutions and the whole thing will solve itself because only the correct solutions 'fit' into the problem which you have represented in the ATCG language. You can do the same thing when you add more variables, and it's just as easy. That is something very hard to do with electronic computers, because they deal with information on the quantity level whereas DNA is able to solve a problem on the problem "abstraction" level itself.

However, conventional *serial* problems are something very hard to do with DNA, because it involves the manipulation of a single strand whereas you would be working in parallel with millions, even billions of strands for NP complete problems. A DNA strand is infismal compared to today's current Si processes, where we measure things in micrometers. DNA is in the single nanometer range. That's several 100 times smaller than a single wavelength of light.

I don't think DNA will be viable for most standard computational tasks, or for a practial turing machine. Biological systems don't use DNA to do logical operations (that I know of), and the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.

This all seems very interesting albeit limited to the lab.

Re:don't hold your breath

[isenguard]

However, conventional *serial* problems are something very hard to do with DNA, because it involves the manipulation of a single strand whereas you would be working in parallel with millions, even billions of strands for NP complete problems.

You are missing the point: NP complete problems (like 3-SAT, which is what they are solving with this DNA computer) are incredibly difficult for serial computers to solve. Nobody seems to be suggesting that DNA computers should be used for serial problems that we can already solve with conventional computers. However, being able to solve SAT (and hence other NP-hard) problems more efficiently is incredibly useful, because SAT problems exist that we can't (and might never be able to) solve using existing techniques.

Re:don't hold your breath

[the_2nd_coming]

the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.

oh god......Microsoft is going to use this for their next generation Office File format!!!!!

now we will have to pay royalties to reproduce!!!!

Re:don't hold your breath

[MarkusQ]

You are missing the point: NP complete problems (like 3-SAT, which is what they are solving with this DNA computer) are incredibly difficult for serial computers to solve.

Not quite. If you have a class of problems, characterized by some parameter n, then for large enough n, the problems in a class that is NP will get harder with increasing n faster than they would if the class was P.

But for any particular instance of a class of problems, it doesn't really matter what the class is--in fact, you can construct example problems that would be NP if generalized in one way, P if generalized another, or even constant time if you choose a perverse "generalization" (e.g., n=date on which the question is posed).

Saying that the problem was NPC is a red herring; what they are actually doing is making a time/space tradeoff which would be hard of conventional computers, and then solving a particular example problem (not the class of problems).

-- MarkusQ

Re:don't hold your breath

[isenguard]

Not quite. If you have a class of problems, characterized by some parameter n, then for large enough n, the problems in a class that is NP will get harder with increasing n faster than they would if the class was P.

True as far as it goes. That's the whole point of complexity: to talk about the growth in the difficulty of solving a problem as the problem size grows. The reason we spend so much time studying NP hard problems is because all known general methods for solving them grow exponentially in the worst case.

Saying that the problem was NPC is a red herring; what they are actually doing is making a time/space tradeoff which would be hard of conventional computers, and then solving a particular example problem (not the class of problems).

The reason I replied to your original comment was that you implied that the work wasn't useful, or wasn't as much of a breakthrough as Adleman claims. Saying that they only solved a single instance isn't relevant: they have a method that works on any 3-SAT problem for which they can construct a long enough DNA chain to represent an assignment, and they have an implementation that actually finds the solution.

Don't forget that the first practical computer algorithm for SAT (Davis and Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, 1960) didn't even have a computer implementation: they demonstrated its usefulness by working an example out by hand!

Re:don't hold your breath

[xenotrope]

"Limited to the lab" is right. The title of this article is rather misleading, since it indicates that the answer had one million components, instead of one million choices. It's far less impressive for a DNA computer to pick one right answer out of a million when you consider that's the only advantage that DNA computers are really said to have.

When I first started reading the article, I thought this was a big breakthrough for security and encryption (knee-jerk reaction, I know). When I saw "million-answer" and "Adleman", I thought he'd found a way to factor an enormous composite number into a million factors. Correct me if I'm wrong, but he is the "A" in RSA, right? I was very quickly disappointed.

This article is a total letdown and, dare I say it, neither news for nerds, nor stuff that matters. The sheer theoretical limitations of this project demands that this sort of thing will never, ever make it into common and public use until every Joe on the street has at least a BS in biogenetical engineering.

There are so many constraints to this kind of work that it will only ever be useful to academics with too much free time. Is it interesting? Sure, for some. Is it useful? I don't see how. When every Linux-loving 14-year-old out there has his own little genetics lab in his bedroom next to his homebrew Apache server, maybe this article will start to stir real interest on this site. This subject is so far removed from "real" computing, by which I mean conventional transistors and whatnot, that it's virutally useless to the computing community. Bravo, Dr. Adleman.

Re:don't hold your breath

[Anonymous Coward]

> Biological systems don't use DNA to do logical operations

Perhaps in the strictest sense, but there are boolean logic machines throughout biology, many involving DNA and DNA-binding proteins.

The classic example is the LAC operon in bacteria. The switch controls an enzyme for digesting lactose (a type of sugar). The bacteria prefers glucose because it takes less work to digest. But if there's only lactose for dinner, it eats lactose. The switch definition:

if (lactose present && ! glucose present)
generate beta-galactosidase mRNA // enzyme for digesting lactose
else
don't do anything.

For a short and very readable introduction to this area, see the classic book A Genetic Switch by Ptashne. Only a basic biology background is needed.

Re:don't hold your breath

[Nagash]

I don't think DNA will be viable for most standard computational tasks, or for a practial turing machine.

No (respected) person in the field of DNA computing thinks that DNA computing will be practical for everyday tasks. It's just too slow. (For that matter, no turing machine is practical. Every try to program one?)

For the record, I (Geoff Wozniak) am a graduate student of Dr. Lila Kari, a well known member of the field of DNA computing. Incidently, Lila was involved in the project talked about in the article.

However, what DNA computing could be useful for in the future is solving problems that can take electronic computers far too long to figure out. Consider the SAT problem that was solved in this article. Suppose we are able to get DNA to solve SAT problems with hundreds of variables. Sure, it might take a week to do it, (maybe even a month), but it sure beats waiting for millions of years.

Quantum computers, however, could change the whole spectrum. However, they are not as evolved as "DNA computers" are right now and I suspect they may take a longer time to be viable.

Biological systems don't use DNA to do logical operations (that I know of), and the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.

Biological systems do a lot more than just copy. Look up work by Landweber and Kari on ciliates and gene rearrangement, for starters. In addition to copy, biological systems also to extracting/cutting, filtering, and pasting/annealing.

You mentioned data storage. Here is where the real benefit of DNA could come into use. The way genes are expressed using only A, C, G, T is quite remarkable. The real advantage of DNA computation lies, imo, in the encoding proerties of DNA. The language of DNA has incredible error-detecting/correcting capabilities. Our work is focusing on learning more about this language and using it for the computational process in some way. I/O would be slow to DNA, but if it can store huge quantities of information, it's worth the effort, especially if better ways for long term storage can be found (of which there is a good chance).

You have to think outside of the conventional computing process to see why DNA computation is so interesting. The problem is that "computers" and "electronic" seem to be synonymous, which they are most certainly not.

Woz

Re:don't hold your breath

[MarkusQ]

The reason I replied to your original comment was that you implied that the work wasn't useful, or wasn't as much of a breakthrough as Adleman claims

I assume you are refering to the post by Hydra; my only prior post on this topic was a reply to you, not visa versa.

Saying that they only solved a single instance isn't relevant: they have a method that works on any 3-SAT problem for which they can construct a long enough DNA chain to represent an assignment, and they have an implementation that actually finds the solution.

But (I claim) they have only distributed the work, adjusting the time required by factors that depends on things like:

The number of DNA strands they use (which goes up roughly as the cube of the liniar scale of their reaction chamber(s), or linarly with cost of reagents, and goes down liniarly with n. The length of time that it takes two strands to bind (liniar with length, IIRC). Chance of mismatch (best case coding, liniar with length, but could easily turn into a birthday problem). Etc.

Note that these are all polynomial factors, and some of them work against you; you haven't really changed the NP-ness of the problem. Yes, this is cool work, and I'm glad they are doing it; no, it doesn't affect the math, any more than faster CPU's (for which I am also glad) do. To me, a "breakthrough" would be something like cracking NPC or proving that that was impossible. Everything else is just technology.

-- MarkusQ

Re:don't hold your breath

[deoxyribozyme]

I believe that DNA computing experiments will soon run into problems involving DNA structure. As an example, there are many well known WC helices that aren't anything like the straight B form structures pounded into the brains of biochem students.

The real future power of DNA computing will undoubtedly involve long stretches of random sequences (flanked by constant primer regions)- otherwise the synthesis of a pool required for any interesting problem would be tremendously difficult. With random single-stranded regions come the problems of structure (see http://ozone.chem.wayne.edu/)

I'm not dismissing DNA computing out of hand. I find whiplash PCR and related papers absolutely cool (David H. Wood, Hong Bi, Steven O. Kimbrough, Dongjun Wu & Junghuei Chen -DNA Starts to Learn Poker). But I find simple WC base pairing boring. And designing double-standed DNA to perform as a stand-alone automaton (http://www.wired.com/news/technology/0,1282,48697 ,00.html) has, imo, the intellectual significance of a bad crossword puzzle (even if all rxns are done in one pot).

I know of at least two papers that will, over the next year, report on success in forcing a low number of nucleic acids to perform serial problems.

Finally, I believe that the nonbiological molecules being forwarded by the likes of Reed/Tour and Heath/HP will win out over the long haul. But one can imagine DNA being coupled to the process.

My $0.02, Ken

Re:don't hold your breath

[sh_mmer]

However, what DNA computing could be useful for in the future is solving problems that can take electronic computers far too long to figure out. Consider the SAT problem that was solved in this article. Suppose we are able to get DNA to solve SAT problems with hundreds of variables. Sure, it might take a week to do it, (maybe even a month), but it sure beats waiting for millions of years.

Except don't forget that the time-complexity of a serial computer is the space-complexity of a parallel computer, for example this one. note that the solution has to be present at the beginning of the algorithm, which for a SAT problem with a few hundred variables would quickly use up all the matter in the universe.

Re:don't hold your breath

[Broccolist]

Of course it's useless right now. It's fundamental research. But to state the obvious, recent "useless" fundamental research on unexpected magnetic effects led to the development of current multi-Gb hard drives, and let's not even get into "useless" semiconductor research in the mid-20th century.

This stuff is interesting because it may represent the future of some fields of computing, even if it's only solving NP-complete problems for scientific applications. Now maybe you are only interested in the few developments that have an immediate, direct impact on you, fine. Personally, I'm not. Just because this technology currently limited to the lab is no reason to be so scathing.

Re:don't hold your breath

[roman_mir]

A computer capable of increasing it's memory size by literary multiplying its memory cells - or growing (of-course I would have to feed it!) A computer that will solve tasks in parallel and will increase its solving power by growing more and more CPUs (brain cells if you will) A computer that has every brain cell connected with every other brain cell (the power is not the number of cells but number of connections between cells) A computer capable of abstract thinking, A computer aware of its own existence, A computer capable of real language communications, A computer that you can communicate with directly with no other input system than your own brain, A computer capable of reproducing itself with various mutations that may or may not improve the next computer generation powers, A computer consisting of trillions of living organisms that combine all computing and storage capacities of every separate organism into one huge organic computer, A computer capable of figuring out who I am without me having to remember any passwords, a computer capable of winning GO, and finally, me being a part of this enormous computing system being able to know everything that is worth knowing all at the same time as writing this goddamn web based application I am currently working on. This is the computer I want.

Re:don't hold your breath

[mgv]

The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really

Actually, we do alot more than that. How do you think that our immune system works? Every immune globulin is coded in DNA. Do you think we have DNA to produce an immune globulin to every possible molecule? Nope. We rearrange our DNA to produce matching (ie., stereochemical gloves that fit a specifically shaped and charged molecule) immune globulin. There may be similar stuff for our sense of smell.

Its alot more complex than that. Just like true neural computing has to do more than just weigh up a series of electrical inputs to a nerve - there are local and systemic hormonal messengers.

Its easy to make a mistake by interpreting a technology only in terms of your current understanding of technology. See my .sig with regard to this.

Michael

Re:don't hold your breath

[Nagash]

Except don't forget that the time-complexity of a serial computer is the space-complexity of a parallel computer, for example this one. note that the solution has to be present at the beginning of the algorithm, which for a SAT problem with a few hundred variables would quickly use up all the matter in the universe.

This assumes one thing: that we continue to use the same encodings we have up to this point. I doubt this will be the case. I'm sure ways will be found to come up with better encodings and methods for solving problems of this scale. The field is only 8 years old, remember.

Woz

Re:don't hold your breath

[sh_mmer]

to the extent that the space complexity of DNA computers can be improved by clever encodings, the time complexity of classical computers can be improved using the same encodings.

that's simply because DNA computers are just a bunch of little computers which can be simulated with equal overall complexity (space complexity X time complexity) by one big computer. i'm not saying that DNA computers (or some other form of super-parallel computers) won't ultimately be much faster than conventional computers (i work with parallel algorithms in my research). what i'm saying is that exponential complexity algorithms won't be implemented in polynomial space and time, even by DNA computers, which is what the previous poster was implying (SAT is NP hard.)

cheers,

What is P vs. NP and why should I care?

[rtos]

Perhaps you are wondering what an NP-complete problem is or what this P vs. NP stuff is all about. You might want to check out the comp.theory FAQ and scroll down to 7. P vs NP. It gives a bit of history and a decent description.

Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.

Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling to multiprocessor scheduling.

Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)

DNA computers

[FrostedWheat]

It's amazing the things possible with DNA computers, little tiny ones implanted in the human brain.

Of course, it won't be long until people are over clocking. Or worse, adding transparent case mods. *shudders*

Re:DNA computers

[Anonymous Coward]

Overclocking is already possible but is highly discouraged by the ATF, DEA, and DARE.

I see now.

[Alien54]

ah, I see.

You took it very seriously because it hit a hot button.

There is a technical term for the comment I made about a DNA based AI computer.

It is called a "joke".

This is because of the cognitive dissonance between the usual attempts at AI using wires and cirsuits and such, the DNA from living creatures, where some form of awareness and intelligence can occasionally be found.

go have yer morning cup of coffee, and relax. perhaps you didn't see the smiley face in the original post.

Re:I see now.

[dollargonzo]

oh, i took it as a joke, just the joke seems to also sum up what EVERYONE thinks...that's all!

QED

Read the article

[lars]

Adleman and co-workers expressed their problem as a string of 24 'clauses', each of which specified a certain combination of 'true' and 'false' for three of the 20 variables. The team then assigned two short strands of specially encoded DNA to all 20 variables, representing 'true' and 'false' for each one.

Clearly the problem was 3-SAT.

Re:I AM NOT A TROLL!

[Anonymous Coward]

Trolls post useless information known as 'crapfloods'.

Useless information? Gee... You mean like this post? -1 Offtopic, please.

Whining accomplishes nothing. If you don't like being moderated down, then start writing ontopic, anti-inflammatory, appropriate, legal, non-offensive posts, and deal with the real cracksmokers in metamod.

P.S. First-posters are not trolls, they're just offtopic.

Errata: First Complex Electronic Solutions

[Baldrson]

the first time that electronic computers solved a complex problem in the 1960s.

Although the author may be responding to Seymour Cray's first supercomputers circa 1960 it is untrue that complex computations weren't being performed electronically until the 1960s.

The History of Unisys shows the earliest milestones with the following one almost certainly qualifying as "complex computation":

1952 UNIVAC makes history by predicting the election of Dwight D. Eisenhower as U.S. president before polls close.

Re:Errata: First Complex Electronic Solutions

[Ed Avis]

That history is quite amusing to read from bottom to top. It shows how highly the Unisys marketroids rate their own importance.

So we have in 1946 'ENIAC developed', and in 1997, with about the same amount of emphasis: 'Lawrence A. Weinbach named chairman, president, and CEO. Unisys Windows NT servers lead industry in price/performance.'.

Comparable to 1960s computers

[isenguard]

According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s.

The description of the problem they are solving corresponds to a 3-SAT (propositional satisfiability with clauses of length 3) instance. In 1962 Davis, Logemann and Loveland published a paper entitled "A Machine Program for Theorem-Proving", in which they described a computer program which could solve SAT problems of a similar size, extending earlier work by Davis and others published in 1960. (You can read the paper in Communications of the ACM if you have a library that goes back that far.) So it looks like their comparison is correct.

The method they are using for the DNA computer is rather crude compared to that proposed by Davis et al, whose procedure is still in use today for solving SAT problems. We can now solve problems with thousands of variables, and actually do useful things in the process (e.g. verify hardware specifications).

Re:Comparable to 1960s computers

[Thing 1]

... proposed by Davis et al, whose procedure is still in use today for solving SAT problems.

Wish I knew about that in high school, my SATs were abysmal.

Good links!

[rueba]

I already knew something about P vs NP but some of these links have really non-technical easy explanations.
I am particularly enjoying the one on the link between Microsoft Minesweeper and NP complete problems
(Yes I remember when it was reported here, but it only linked to the guys academic paper which was too deep for me)

Bizzare order

[nusuth]

That means you can have millions of solutions and the whole thing will solve itself because only the correct solutions 'fit' into the problem which you have represented in the ATCG language.

Well, the way you stated the problem, all problems are solvable (on a digital computer) in linear time wrt problem representation The most amazing order I've seen so far.

Hint: char alphabet[]="AGCT";

Short answer NO

[lars]

Well, any computer can be used to attack crypto algorithms, it's just a matter of whether the computer can do so in a reasonable amount of time (like, say, the lifetime of the universe :) ). With current technology, it is not possible to break these algorithms, because the problems they are based on are believed to be hard. You can view this DNA computer as simply just being a new architecture, like Intel or SPARC. It's cool, but it has no effect on the dificulty of problems. The computing models computational complexity theory is based on are mathematical, and do not depend on any physical implementation of a machine.

Quantum computers are a slightly different story. They are theoretically non-deterministic machines that can solve all problems in NP in polynomial time. In theory, with a big enough quantum computer you could break all currently used encryption schemes, but in practice, no one has really come close to building a quantum computer to actually do anything non-trivial let alone useful. I've heard it suggested (I don't really know anything about quantum mechanics, so maybe the physics geeks in the crowd could comment on this and let me know if I'm full of crap) that it may be the case that while a quantum computer may be able to solve NP-hard problems in polytime, the difficulty and complexity of building such a machine might be proportional to the difficulty of solving the problem in P.

If this is the case, then even if it's theoretically possible to build quantum machines to break known crypto algorithms, in practice it would be infeasible to do so. If the complexity of building the machine doubles when you add a qbit then you may as well just use a deterministic computer and wait a few billion years for your answer.

Re:Short answer NO

[ActiveSX]

> You can view this DNA computer as simply just being a new architecture, like Intel or SPARC.

Yes, but can it run NetBSD? :)

Re:Short answer NO

[Ronin SpoilSpot]

The interesting feature of DNA computing is that it is massively parallel, maybe potentially much more than anything we have build electronically so far. Also, it is not restricted to a specific clock cycle, which makes it hard to define the "computing power" of a bowl of strands. Still, they are not equivalent in power to Nondeterministic Turing Machines in general, so DNA computers will not necessarily be the end of all NP-complete problems. Probbly only those of a limited size.

Any instance of a NP complete problem can be solved by a deterministic computer in a fixed time. Often, throwing more computers at the problem lowers the time linearly, so for that specific problem, the time can be as low as wanted. It is just that the number of computers you have to throw at the problem grows very fast as the problem size grows. What they have shown here is that DNA computing works at somewhat large problems, but 2^20 could be bruteforced just as easily.

Now, you calim that Quantum Computing can solve ALL NP-complete problems. That is not known. The group of problems that are polynomially quantum-commputable are a subset of the NP problems which is not known to include any NP-complete problem.
(We don't know that it doesn't, since that would mean that we knew that PNP, and we would have heard that :).

Factoring can be performed effectively by a qunatum computer, but is not NP complete.
(It is in NP intersect coNP, incidentally).

/RS

Re:Short answer NO

[a random streaker]

> You can view this DNA computer

Finally a way to merge Natalie Portman and Beowulf Clusters.

The A in RSA

[Anonymous Coward]

This is Leonard Adleman .. the A in RSA, difficult to tell from his homepage .. unless u dig. i guess he keeps in low key.

Ironic, by showing how to do 0computation with DNA he may be undemining RSA!

It needs to be said...

[Anonymous Coward]

...imagine a beowolf cluster of these babies...

Obligatory

[lars]

Imagine a Beowulf cluster of these!

But seriously, I imagine these things must be pretty slow, since they are powered by chemical reactions. I don't forsee one of these babies supplanting my desktop any time soon. Of course, the whole point is that this shows the power of genetics, and it is amazing in that sense, to think that life is basically created by computer programs. Fortunately Microsoft hasn't gotten into the DNA software market yet, I'd hate to have bugs growing out of my skin and stuff. :)

Re:Obligatory

[Fiver-rah]

I imagine these things must be pretty slow, since they are powered by chemical reactions.

DNA base pairs are not held together by chemical bonding. That would be a really, really difficult. They're held together by hydrogen bonds. The breaking and formation of hydrogen bonds takes on the order of picoseconds (it's the same timescale as rotations in the medium, since that's the basic mechanism for their breaking). Furthermore, they can break and form in parallel.

You can read more about the mechanism for base pairing here or if you want to see google render the pdf here .

Re:Obligatory

[SpinyNorman]

That's like saying that the brain is slow because it's based on chemical reactions...

The whole point of this "DNA computer" is that it's massively parallel - it evaluates all possible solutions in parallel. Increase the size of your problem .. no biggie - just add another pint of "computer".

Re:Obligatory

[lars]

That's like saying the brain is slow because it's based on chemical reactions...

Yes, exactly -- what would you use if you wanted to factor a 256-bit prime, your brain, or a computer? Similarly, this technology isn't going to be useful for solving general computational problems. I imagine it would be very useful for controlling biological systems, but it's not something I'm going to pull out when I want to do some number crunching! That's my point.

it evaluates all possible solutions in parallel.

Which means it's limited by the number of solutions you can represent in parallel. You're not going to be able to use this to evaluate 2^1024 possible solutions in parallel, unless there's funky quantum mechanics stuff involved. There probably aren't that many particles in the universe.

Increase the size of your problem .. no biggie - just add another pint of "computer".

Not exactly. For a problem like 3-SAT (the problem they solved here), a linear increase in the size of the problem input = an exponential increase in the number of solutions they need to evaluate. If they doubled the input size from 20 variables to 40, they'd need to evaluate 1 TRILLION solutions in parallel instead of 1 million. So they'd need the equivalent of 1 million of these DNA computers running in parallel. I'd consider that more than "just another pint".

Re:Obligatory

[Rubyflame]

Yes, exactly -- what would you use if you wanted to factor a 256-bit prime, your brain, or a computer?

You can't factor prime numbers. They're already factored.

Imagine...

[WetCat]

if a byproduct of that solutions of problems
becomes a monster (some cells actually incorporated problem DNA-s).
WoW!

Re:Imagine...

[mofolotopo]

Odds are it would do nothing. Without an intron, a strand of DNA isn't translated into protein and therefore does nothing. The odds of it being inserted into a coding sequence are less than one in ten, and even if it was the odds of it producing some sort of constructive mutation that would do anything interesting are vanishingly small.

This post has everything I hate, but...

[Anonymous Coward]

Goddman. A natalie (not attractive) portman post, the goatcex crap (no pun intended), and worst of all, unforgiveable,a star wars reference.

I'm throwing up now.

However, I laughed. Something about "I DO IT WRONG" makes it all okay in the end. Again, no pun intended.

Preparation is extensive

[Jobe_br]

It seems to me that the amount of preparation that went into constructing the long strands and each of the truth sets is extensive. For this type of computing to become useful, it would appear to me that this construction of the parts necessary to carry out the computation would need significant work. I am very, very hopeful that DNA based computing as well as quantum molecular based computing will begin to make rapid gains in the very near future. The potential to astronomically increase the available computing power is there, I've read all the theories. It just needs to be made to happen :)

Just imagine ... quantum computing devices become common, as do DNA based computing devices - each in their own niche, possibly (neither device may be promising as a 'general computing' device, but used in conjunction they may complement each other) and the article previously posted about table-top fusion from the collapse of bubbles provides us with practically limitless and clean energy to drive the energy needs of all our computing devices. I can't wait :)

Add to that the possibilities for human augmentation by cybernetic implants and I feel that the day of Gibson's Neuromancer may be soon approaching. As the geek I am, I can't wait :)

Re:Preparation is extensive

[Jerf]

Each of the possible 1 048 576 solutions were then represented by much longer strands of specially encoded DNA, which Adleman's team added to the first cell.

Granted I'm not a bio-engineer, but it's very difficult for me to believe that DNA will ever solve a problem faster then the computer can.

For this problem, millions of DNA strands were generated. I guarentee you the researchers didn't do it by hand. In the time the computer was instructing the hardware on how to make any given solution, it could have checked a thousand solutions. And the speed is accelerating.

Maybe, just maybe, if the strands could be generated automatically by a gene-gen'ed life form, except for the query strand, this could keep up with conventional silicon. But that's a tough nut itself.

I'm more intrigued by the QM computers... and I don't really believe in them, either.

(Biological computing may someday take off. But I don't think it's going to involve DNA. DNA is not meant for computing in the sense most of us find interesting. The gymnastics necessary to answer this simple question demonstrates that, and unlike conventional computers, where there has always been a clear path of progress, exactly what part of this computation is going to be streamlined? Millions upon millions of unique strands must be generated; what's the equivalent of shrinking the transistor by a factor of 2? I'm not holding my breath.)

Re:Preparation is extensive

[Jobe_br]

I think where this (DNA computing) and quantum computing may come into their own is in massively parallel systems. Imagine being faced with a task that would take a single processor working in serial millions of years. Imagine how much faster it would be if you could take a O(2^n) problem and throw n processors at it. Not very feasible with silicon, but what about DNA or QC? That, I believe, is the magic here ... by their very composition, these types of computing allow massively parallel processing to occur. One chemical reaction that takes place in a fraction of a second could be equivalent to a single processor going through quadrillions of calculations or a farm of serial processors going through trillions of calculations each. The possibilities are intoxicating!

Re:Preparation is extensive

[Jerf]

Not very feasible with silicon, but what about DNA or QC?

DNA: Infeasible. You're still stuck with manufacturing 2^n processors, and this is not a trivial problem. You get into situations where "The entire universe must consist of DNA to solve this problem" in short order. 2^n problems are quite, quite hard.

Also, the parralelism breaks down, the more DNA you use, something I don't see much acknolegement of. For truly huge problems, if the solution involves strand A finding strand B amoung 2^50 strands, that may take a while, i.e., never happen.

QC: In theory yes. In reality, I'm quite skeptical of true QM. It requires Nobel-Prize-winning work in isolating the quantum states of a system from outside interference for any significant quantum computer, and that may still be trivializing the difficulty. I'm not holding my breath for "strong" quantum computing.

One chemical reaction that takes place in a fraction of a second could be equivalent to a single processor going through quadrillions of calculations.

No. Chemicals live in the real world too, where they have volume, mass, and take real time to react. I'll buy thousands, but not quadrillions.

The possibilities are intoxicating!

Yes, the hype proves that.

Re:Preparation is extensive

[Jobe_br]

If a DNA strand can divide and replicate in seconds (or less) and that strand has billions of CGAT pairs on it, and this is what DNA based computing is trying to harness, then quite literally, billions of calculations or more can be computed in a fraction of the time it takes a serial processor. I'm far from an expert, but I think you're quite missing the point of DNA and Quantum based computing. These forms of computing *break* the typical way processing takes place, which allows them to compute at orders of magnitude faster than traditional computing devices.

Millions of dollars is being spent researching a pipe-dream. It may or may not end up being possible, but the theory is definitely rock-solid else the grants would never have been approved. You're attacking the theory of these types of computing devices (particularly in your bit about DNA) and that's really not up for discussion. What's up for discussion is simply if it will ever end up working they way its intended.

Re:Preparation is extensive

[Jerf]

If a DNA strand can divide and replicate in seconds (or less) and that strand has billions of CGAT pairs on it, and this is what DNA based computing is trying to harness, then quite literally, billions of calculations or more can be computed in a fraction of the time it takes a serial processor.

It is not; DNA computing does not use the replication of DNA.

I'm far from an expert, but I think you're quite missing the point of DNA and Quantum based computing.

DNA maybe, quantum most assuredly not; my opnion on that is well considered.

These forms of computing *break* the typical way processing takes place, which allows them to compute at orders of magnitude faster than traditional computing devices.

IF AND ONLY IF THEY WORK.

You're attacking the theory of these types of computing devices (particularly in your bit about DNA) and that's really not up for discussion.

Not clear on how science works, are we? Theories are always up for discussion, because that's directly related to is simply if it will ever end up working they way its intended. I'm saying no to "strong" QM, and I doubt it for DNA. DNA is no stronger that I can see then conventional computing, it just jumps us up a few factors of magnitude, which corresponds to a problem size increase of very little. (Study what NP-Complete means.) I'm beginning to wonder if it's mostly Biologists studying this.

QM does open new possibilities, but only is some improbably conditions exist (complete or nearly complete isolation from outside influences for many many milliseconds for many many qubits? unlikely!), which are probably impossible.

A few questions

[sean23007]

This is interesting, but would it have worked at all if the scientists did not know the answer already? I mean, they set up all the variables, and then they set up all the possible answers, and the DNA just matched up with the one that they already knew to be correct. What if they didn't know which one was correct? What if there were a billion possible answers? Would they have to program them all in? At what point is it actually faster to use a computationally inefficient conventional PC instead because the compiler does the brunt work for you? Is this DNA method ever faster?

Obviously, there are a lot of questions to be asked about this, but it will be very interesting to see what happens when somebody develops some kind of compiler for the DNA computer, and you can just input an equation and some parameters and in several minutes you have the answer... But until then, this doesn't seem all that useful. On the other hand, it is fascinating research, and by all means, they should continue research on it.

Re:A few questions

[Anonymous Coward]

The person doing the actual experiment had no knowledge of the answer! How do I know this. Because I was there!

only 1048576 solutions to check?

[Anonymous Coward]

My computer could do that in under a second. This is news WHY?

Re:I AM NOT A TROLL!

[Anonymous Coward]

best trolls get +5. i'm almost serious.
when you tell people what they wish to hear, you dont need to be accurate and even less imaginative.

be first and be obvious. rant.

i'm waiting for something like "standard counterargument library" where a bot could paste a backfire before anyone else on the most common crap so that people could think with their own brains instead of trying to become the collective mind of slashdot group x or whatever.
this probably wouldn't help a bit though.

truely useful

[negativekarmanow tm]

the calculation of interactions between many atoms or molecules.

So their going to use the interactions between many atoms and molecules (DNA) to calculate the interactions between many atoms or molecules? Sounds like writing a PS2 emulator for the PS2

Anyway, I'm not going to use this until it comes with a decent GUI and a .NET backend.

42

[edoug]

As a testimate to the parallel computing power of DNA computers, an entire planet of DNA computers has produced the answer to the universe. However, now we must wonder as to what question this answer applies....

Re:42

[mrgunntm]

Damn, you beat me to 42.

already done...

[oo7tushar]

The details are a repost, this technology is "old" as in they did this same problem with travelling salesmen 2 years ago. Details were posted in SCIAM.com

Recent 3-SAT results for "normal" computers

[Alea]

The following are results on 100 variable, 460 clause, "hard" random 3-SAT problems running on a PIII 750. The results are averaged over 100 repetitions of 1000 variables (some solvers are stochastic which is why multiple runs are used). The result shown is the average number of seconds required to solve a single problem once.
Note, these problems are 5 times larger than the one solved by the DNA computer and likely much harder (the DNA one sounds very underconstrained).
Both complete and incomplete solvers are shown:

DLM 0.00406513
Novelty 0.00560927
Novelty+ 0.00325692
WalkSAT 0.00759083
Satz 0.00557251
zChaff 0.00800162

Note: Things don't really get interesting until you get up over 500 variables for hard, random 3-SAT.

Re:Recent 3-SAT results for "normal" computers

[Alea]

Sorry, that's "100 repetitions of 1000 problems" (not variables).

It's important to realize...

[sketchy_gomez]

...that DNA computation offers no theoretical advantage over Turing machines. That is, problems that are thought to take an exponentially increasing number of steps on a regular computer still do with the DNA computation model. The DNA method requires that every combination be exhaustively generated, and therefore the number of molecules required grows exponentially with the input size. Of course, the DNA method offers some practical advantages over today's computers (when it comes to this type of combinatorial problem.) The computational elements (DNA molecules) are very small and can "swim around" in three dimensions to make many more combinatorial "decisions" than could be hardwired onto a piece of silicon today.

it's already in "Applied Cryptography" (B.Schneier

[rkit]

This is not exactly news. The second edition of "Applied Cryptography" by Bruce Schneier already mentions DNA Computing in the discussion of key size.

According to Schneier, Adleman was able to solve a Directed Hamiltonian Path Problem with 7 vertices already in 1994. It is interesting that it took 8 years to get from 8 to 20 vertices. The difficulties seem to be enourmous.

Allthough this seems to be excellent research, I still doubt that this is significant for solving real world problems. After all, this is a brute force search (although a massively parallel one). But there are physical limits to consider: there are ~10^50 atoms on this planet, but this only in the order of 42!. (read faculty of 42...) So 42 may not be the answer after all, but the size of the problem...

Modern algorithms for discrete optimisation can do much better than this. Travelling Salesman Problems in the order of several thousand cities have already been solved.

Didn't Adleman do this something like 9 years ago?

[Owensellwood]

I remember reading an article in Dr. Dobbs journal from something like 1993 about how Adleman used DNA computation to solve an instance of the travelling salesman problem. How is this work really revolutionary then, aside from demonstrating the use of molecular computation techniques on a more complex problem. As far as I can tell this isn't 'news' so much as it has already been done, published and publicised before, by the same physicist/mathematician/biochemist.

please put this in perspective

[knulleke]

The problems that can be solved in a practical manner with dna computing are small. For real problems, you need a sea full of dna. Bummer.

not new, not news

[feed_me_cereal]

I remember reading an article about this in a class I took arround this time last year. And it wasn't even a new article... Very interesting tho, nice implementation of parallel computing :)

Correct answer: maybe

[feed_me_cereal]

> You can view this DNA computer as simply just
> being a new architecture, like Intel or SPARC

nope, Intel and SPARC are serial architectures. This DNA computing is fundementally different. It's actually trying solutions in parallel. Since all the DNA chains are trying to link together at once, you can view this as simultaneous computations to the order of some number relative to the ammount of DNA you've got in your tube. In this way, you can view the DNA computations as more relative to quantum computing. The only problem is, there's a lot of time and money involved in setting up the ccomputation, and in finding your solutions from the muck. Whoever figures out a way to use DNA to crack encryption codes will probably really really really want to figure out what's in those files!

I read an article on this last year for a class I was taking, so it's not really new, as this article states. You should take a look arround the web for a good article and give it a read, it's very interesting.

Re:Correct answer: maybe

[lars]

nope, Intel and SPARC are serial architectures. This DNA computing is fundementally different. It's actually trying solutions in parallel. Since all the DNA chains are trying to link together at once, you can view this as simultaneous computations to the order of some number relative to the ammount of DNA you've got in your tube. In this way, you can view the DNA computations as more relative to quantum computing. The only problem is, there's a lot of time and money involved in setting up the ccomputation, and in finding your solutions from the muck.

Actually, I disagree. Quantum computers are non-deterministic. These DNA computers, while being massively parallel, as you say, are still deterministic. If you can test a million solutions at once in parallel, that's great, but all it does is speed things up by a constant factor over trying them one at a time. It doesn't turn a super-polynomial time algorithm into a polynomial time one, because there's a limit to how many computations you can do in parallel.

On a quantum computer or some other non-deterministic machine, the idea is that you can essentially perform all computations (with no limitation on how many) in parallel.

Re:Correct answer: maybe

[mgv]

These DNA computers, while being massively parallel, as you say, are still deterministic.

Yes. To put it in perspective, though, the average DNA base pair has a molecular weight of 610. So one mole of the substance (ie. 610 g) contains 6.022 x 10 e+23 base pairs.

So, assuming that it takes you 10 days to set up a computation - approximately 10 e+6 seconds, you have 6 * 10 e+17 computational units per second. This assumes the computation time is trivial (which it is, compared to the set up time of 10 days do make all the DNA).

Lets say that again. 600 000 000 000 000 000 computations per second. In a large beaker containing a few litres of solute.

Of course, each unit only holds a quaternery bit of information (ie., one of four states for the four kinds of nucleotide).

At the moment we have computers that can run in the GHz range, ie., 2 * 10 e+9 computations per second.

A DNA computer will be able to operate at at least 8 orders of magnitude faster than any current conventional computer, and potentially at 10 e+12 times faster with increased amounts of DNA and faster setup times.

It may be deterministic, but it will take us another 25+ years to get to this point on the intel roadmap - which of course should derail before then. In other words, this technology is faster than anything that can be or is likely to be done on silicon.

My 2c worth.

Michael

info from the inside

[areiosoltani]

let me shed a little info on this work for you guys. i'm a graduate student working in len adleman's lab--i'm not an author, but i am very familiar with the details of the project. first off, concerning the complexity of the problem: we like to say that this is the first truly non-trivial problem solved with a DNA computer. len's original traveling salesman problem (solved in 1994 and published in Science) has something like 4 cities and could be easily solved by a human with pen and paper in a matter of seconds. subsequently, several other NP-complete problems have been attempted: most notably the "knight problem" (how many and where can one place knights on a chessboard so they cannot attack each other) and 3-CNF-SAT (3-conjuctive normal form satisfiability) with no known polynomial time algorithm (not including quantum polynomial tome algorithms). this work is a 20 variable instance of 3-CNF-SAT, with a combinatorial diversity of 2^20 possible outcomes, meaning ~ 1 million possible solutions. the 3-CNF-SAT problem was contrived to produce only 1 possible combination that would satisfy the formula. for a human with pen and paper, this problem would take several hours, if not days, using a brute force method of attack. an electronic computer, however, would solve it in a matter of seconds. so to draw an analogy, the DNA computer is probably somewhere near the ENIAC was in the 1940s. Electronic computer development was growing rather slowly until the development of the transistor in the 1950s, and we have been benefitting from Moore's Law ever since. a similar technological breakthrough will be needed for DNA computers to seriously rival the computational power of silicon.

Re:info from the inside

[Anonymous Coward]

And it was done in a blind fashion! Now that is the detail, Len and Nick would have said in the press release.

heheh :)

tip of the iceberg...

[areiosoltani]

I don't think DNA will be viable for most standard computational tasks, or for a practial turing machine. Biological systems don't use DNA to do logical operations (that I know of), and the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.

this is not entirely true. nucleic acids are responsible for quite a few things in the cell. yes, DNA is not very reactive, designed to be a stable archival form of genetic material, but RNA (ribonucleic acid) is a different story. derived from DNA, it has a 2' hydroxyl (-OH) group on its sugar (hence the name ribo- instead of deoxyribo- which has a 2' hydryl (-H) group) and is much more reactive, causing cleavage, ligation, and other enzymatic modifications. there are programmed errors and very regular processes in the cells, things like SOS DNA repair, nonhomologous end-joining, and crossing over, that can result in modification. there is so much here to study it can make your head spin! so don't count any of it out =)

The 'A' in RSA

[Anonymous Coward]

As a grad student at MIT, Leonard Adleman helped invent the public key crypto algorithm know as 'RSA'. The other two gents were Ron Rivest and Adi Shamir (the 'R' and the 'S').

Why DNA computing will never be practical

[lukesl]

There is one serious flaw in DNA computing that people are sweeping under the rug, and that's that although the amount of time needed to solve the problem does not increase exponentially, the amount of DNA does. Off the top of my head, I don't know the amount of DNA needed to perform a given calculation, but one of my professors who works on this sort of thing showed us once that a calculation that could be done in a reasonable amount of time on a standard desktop computer would require more DNA than there is on earth. I'm sure there are ways to increase the efficiency of the process, but this is still a fundamental limitation of this type of computing.

Re:Why DNA computing will never be practical

[Anonymous Coward]

That's interesting. That's the first time that I've heard that.

Question to Life the Universe and Everything

[Anonymous Coward]

What is 6*7?

Past /. article questioning what would happen if..

[3seas]

What would happen if NP-Complete was solved?

Many responses (IIRC) were regarding encryption encoding...

several days after that article I ran across something that
suggested the potential benefits far outweighted not doing it.

Something regarding Space as in outer space and it's safety of us in it.

Anyone have links to such information, as I seem to have forgotten and lost out of browser cache the link.

Re:Past /. article questioning what would happen i

[3seas]

How is solving the NP-Complete problem useful to NASA?

Amdahl nit-pick.

[Christopher Thomas]

In other words, this technology is faster than anything that can be or is likely to bedone on silicon.

...For problems that are easily parallelized to order 1e24 nodes ;).

On the other hand, rendering Quake is massively parallelizable...

N = 1 - P = NP

[sorbits]

Now we just need to show that N = 1... :-)

Article on "How a DNA Computer Works"

[scubacuda]

Printable version of the article found here.

(This is a good starting place if you want to know the basics.)

Re:Correct answer: No

[lars]

You are missing my point.

My point is that if your algorithm is exponential time, I can ALWAYS beat your machine. All I need to do is double the size of the input I give you, and you're forced to SQUARE the speed of your machine to keep up. The only way you can build a machine that can defeat me is if it is a non-deterministic machine (which DNA computers are NOT), or if P=NP and you manage to find a polytime algorithm, which is unlikely.

Consider your example of a 610g DNA computer. And forget about the setup time and let's assume you can perform 10^23, or let's say 2^80 computations per second, and that you never have to intervene to re-configure the machine after exhausting the solutions you're trying. It would still take you 2^944 seconds to solve a 1024-variable instance of 3-SAT. Even if you build one of these that uses 610kg of DNA, the factor of 2^10 speedup would be insignificant. Now you can solve the problem in 2^934 seconds -- big deal! In fact, you could NEVER solve a 1024 variable instance of 3-SAT by naively testing all possibilities using a DNA computer because there aren't enough particles in the universe to represent even a tiny fraction of the solutions!

Maybe you know all of this already. But the poster I was responding to suggested (at least in my interpretation of his post) that these DNA computers are comparable to quantum computers, and that "maybe" eventually they could be used to solve hard problems such as those which are used in cryptography. And that's still absolutely false, unless P=NP, since there are crypto algorithms based on NP-complete problems. Even those which aren't (factoring) are believed to be hard enough that they probably aren't vulnerable (only current key sizes would be).

Re:Correct answer: No

[mgv]

You are missing my point.

I'm not missing your point. I understand the difference between having massively parallel system and something that is not deterministic

In fact, you could NEVER solve a 1024 variable instance of 3-SAT by naively testing all possibilities using a DNA computer because there aren't enough particles in the universe to represent even a tiny fraction of the solutions!

Thats a strong statement. It assumes that all solutions have to be present at once, not sequentially over time, or indeed that a DNA computer has to have all the solutions prefabricated in the first place. It is possible that DNA computers could assemble the answers from base pairs, for example.

My point is that if your algorithm is exponential time, I can ALWAYS beat your machine.
As I understand it, quantum computing currently has extreme scalability problems going beyond a few (? 11 AFAIK) qbits, as its hard to make a molecule big enough to hold all the quantum states.

So you make that comparison based on my worst case scenario (that every answer has to be prefabricated), your best case scenario (that you can read the quantum state of a large molecule), and the assumption that you can simply increase the complexity of a problem until a non deterministic approach is faster.

Personally, I was just commenting that DNA compting is very, very fast in principle. Perhaps we ought to rething 128 bit key lengths even on the basis of this. By the way, if quantum computing becomes practical, just how long will the key length need to get :) :) :)

My 2c worth

Michael