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

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?

[Lictor]

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

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.

And in 5 years Microsoft will say...

[Ozan]

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

Which OS?

[Gangis]

Which OS did they use? Microsoft DNA?

*rimshot*

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.

;-)

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?!

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

[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

[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

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

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.

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

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

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