DNA computers may be the platypuses of the computing world - they're physically unusual, with odd component parts designed to solve special problems. Components of DNA computing include such nonelectronic items as test tubes, enzymes, electrophoretic gels and beads, gold-plated glass slides, E. Coli bacteria and, of course, deoxyribonucleic acid (DNA).
DNA computing was first used successfully in 1994 by Leonard Adleman, a professor at the University of Southern California in Los Angeles, to solve a version of the Hambletonian Path - the so-called traveling salesman problem. Several other prototypes have been created since then. All of them have been used as proof-of-concepts to solve scaled-down versions of larger, more intractable problems.
Aside from its curiosity value, DNA computing's claim to fame is that it takes advantage of a kind of massive parallelism that isn't available electronically or even optically. Inside a test tube, literally trillions of possible solutions can be generated in parallel. The problems that can be solved, however, need to be rigidly specified. None of these prototypes point a clear path toward mainstream computing.
The Breakthrough
Adleman used DNA to solve a seven-node traveling salesman problem. The question was: Given a set of nodes and directed vertices between them, is it possible to construct a path that starts at Node 0, ends at Node 6 and passes through all of the other nodes only once?
It's the kind of resource-allocation question that might get the attention of someone in the front office of an airline.
An enterprising information technology student might be able to take out a pen and solve the seven-node problem more quickly than Adleman's DNA computer, which took about a week. But imagine if the problem involved a traveling salesman who had to visit 200 nodes. Problems like this are called NP-complete problems, meaning their complexity grows exponentially as the specification of the problem increases linearly in size. When they get big enough, they can stop an electronic computer in its silicon. On the other hand, it has been estimated that using Adleman's massively parallel DNA method to solve a 200-node graph could require a chunk of DNA that weighs more than the Earth.
In solving the seven-node problem, Adleman assigned DNA codes to each element of the problem, which meant one code per node and one related code per directed vertex. In a test tube, he mixed versions of these DNA codes, which annealed to produce an unknown number of solutions, most of them probably wrong.
Adleman then filtered out the wrong solutions by applying a series of criteria that worked logically and could be implemented in a test tube.
Security Threat
The promise of this technique is that any problem that could be posed in a way that corresponds to the one Adleman solved could theoretically be solved as well.
Adleman and others have suggested that this method could be used to crack the U.S. government's Data Encryption Standard (DES), which is used to encode sensitive data for transmission. Employing one of 256 keys, DES is almost uncrackable by the most powerful supercomputers.
But a DNA-based method that could test all 72 quadrillion keys at once might have a chance. Though the DES services company RSA Data Security Inc. in Bedford, Mass., has stated that "with a large enough key, one should be able to thwart any DNA computer that can be built."
A group of researchers at NEC Research Institute Inc. in Princeton, N.J., reported in 1997 that they had constructed a DNA computer to solve a "maximal clique problem" involving six nodes with 11 connections. The question was: Given a set of nodes and a set of connections, what is the maximum number of nodes that are directly connected?
After assigning codes to the components of the problem, generating DNA to match the codes, mixing the DNA so it could anneal and filtering and sorting the DNA, they incorporated the remaining "solution" DNA into viruses and had the viruses infect E. Coli bacteria. The viral DNA in the bacteria multiplied (in the same way that viruses make people sick), and the "solution" DNA was multiplied also. There was then enough to sequence it and find the problem's solution.
Gold-Plated Research
Researchers at the University of Wisconsin in Madison have used another type of DNA computer to solve a "satisfiability problem," in which binary numbers are tested to see if they satisfy a formula and produce "binary true," or the number 1. Their prototype had to test 32 sequences. A problem scaled up by a factor of four would have had to test 1 million sequences.
This effort used DNA strands attached to a gold-plated glass slide so the solution DNA wouldn't be accidentally washed down the drain. Wrong solutions were broken down and washed away.
As has been pointed out, most of these DNA computation schemes involve breaking down the computer every time they are used. Unlike electronic instructions, which can be rerun with the push of a button, there may be more setup required to run a DNA computer.
A programmer who is used to debugging code by running a sample case over and over again may have to come up with a new paradigm. What might, in an electronic environment, appear to be a simple, algorithmic change, such as requiring Adleman's salesman to visit one of the nodes twice, without specifying which node, might, in a DNA environment, require an entirely new system of filtration and sorting, and possibly a different approach to specifying the problem.
"DNA computers are unlikely to become stand-alone competitors for electronic computers," says Adleman.
Their most productive application, suggests John Reif, a professor at Duke University's computer science department in Durham, N.C., might be in streamlining the decoding and processing of natural DNA that's being done in the Human Genome Project and in crime laboratories.
Matlis is a freelance writer in Newton, Mass. He can be reached at jmtgpcmcm@aol.com.
Click to see chart in PDF Format