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