Slashdot Mirror

← Back to Stories (view on slashdot.org)

DNA Solves Million-Answer NP-Complete Problem

Posted by timothy on from the combinations dept.

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

6 of 169 comments (clear)

  1. Real article by mnordstr · · Score: 5, Informative

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

    1. Re:Real article by bcrowell · · Score: 5, Informative

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

      --
      Find free books.
  2. And in 5 years Microsoft will say... by Ozan · · Score: 5, Funny

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

  3. It's only a matter of time... by guttentag · · Score: 4, Funny
    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?!

  4. What is P vs. NP and why should I care? by rtos · · Score: 5, Informative
    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. :)

    --
    -- null
  5. Re:don't hold your breath by Nagash · · Score: 4, Interesting

    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