DNA Computing: A Possible Efficiency Boost for Specialized Problems [Archives:2000/45/Science & Technology]

Prof. Salem
Al-AbdelRahman
Some problems that are amenable to DNA computing are optimal shop scheduling and the longest path in a graph. Additionally, other good candidates for DNA computing are cryptography, problems from computer-aided design (CAD) such as checking out the correctness of circuits or protocols, and factoring.
R. J. Lipton (Professor of computer science at Princeton University – USA) has developed an approach to solving the Satisfaction Problem with DNA, thus demonstrating how DNA computers work as powerful search machines. The satisfaction problem is central to computing and complexity theory. It attempts to answer whether, for a given Boolean expression A, values can be assigned to the variables in A such that A is true. For a satisfaction problem with n variables, an electronic computer must test 2n variables one by one, and if n is large, this takes a long time. However, the DNA approach checks all the variables simultaneously, solving the problem much more efficiently than the traditional approach.
Working with his students Dan Boneh and Christopher Dunworth, R. J. Lipton has also come up with a method for using DNA to break the data-encryption standard knows as DES, developed by the National Security Agency. DES makes use of a single key, among 256 keys, to scramble messages. To break the code, a would-be codebreaker must test each of the 256 key one by one, which would take impossible long on a conventional computer. However, in the DNA approach, all the keys can be searched simultaneously for the correct one. The key are encoded in strands of DNA and processed in a series of steps involving extractions, replications, and other biological operations. Breaking the first key would take months; however, subsequent keys can be cracked in a matter of minutes. DNAs computational potential relies on properties such as its massive parallelism, its capacity for information storage, and energy efficiency. DNA-based computers use about one trillionth of the space that conventional computer do to store data.
Other possible applications, such as using DNA in the manufacture of drugs, have also been proposed. Some of these applications are closer than others to practical ways of implementation. In the view of many DNA-computer scientists, once a killer app-an important application for which DNA computing is better suited than any other method- is found, the field will leap forward to the next sage in its development. Additional resources will then be forthcoming, together with industrial support and hundreds more practitioners. Even at the present stage, however, a researcher can locate more than 100 technical papers on DNA computing.

Several Specialized Uses
Like other fledgling technologies, DNA computing has its doubters who contend that the method claims more than it can ultimately deliver. However, to evaluate the merits of a DNA-based computer objectively, critics must take into account that it is not a general-purpose computer, but a rather a machine geared toward specialized uses. DNA computing seems best adapted to search problems and to problems that required vast amounts of memory (note that 1012 strand of DNA, each 1000 units long, are equal to 1000 Tbytes of memory).
Consequently, the technology should be judged on its abilities primarily in these two arenas, and not as a panacea for computing problems in general.
In the first arena, DNA appears to be best suited to searching for up to 60- or 70 bit patterns, in situations in which the pattern in question is relatively easy to describe. (Ad traveling – sales – man problem fits in this category.) A general rule of thumb for search problems on computers is that, for a n-bit pattern, the solution will not take fewer than 2n searching steps, although in practice, programmers can usually find heuristic algorithms that are much more efficient than this. For other cases, however in which there is no clever, heuristic fix, DNA computing maybe the optimum method for solving the problem. One example is the aforementioned DES code. The DES has a key or pattern size of 56, and so DNA can solve for the key in approximately 1000 steps, each step representing an operation done on the DNA. More recent codes, however, in which the key size is 80 or 128, maybe beyond the capacity of DNA to solve.
DNA may also prove more efficient than the traditional computer with algorithms that require immense amounts of memory to solve, that is, more than 1000 Tbytes. The DES problem fits this category. Richard J. Lipton has considered another prospective example, that of three-coloring a graph, that exploits DNAs large memory capacity. Three-coloring is a kind of search problem, and with DNA computing it can be solved by an inductive algorithm that reduces the time required from 3n to 1.5n, where n is the number of vertices. A conventional computer would be unable to store the huge number of coloring involved in solving this algorithm. Hence, DNA may be the method of choice.
One difficulty that must be overcome involves correcting the errors that result from handling a DNA computer. The error rates that are observed when extracting DNA with a specified pattern from a test tube are typically about 1 part in 106. Moreover, DNA decays with time; this problem particularly affects computation that takes months to complete. However, work is currently being done to demonstrate that error-prone computation can be re arranged so as to make them virtually free of errors.
Perhaps it will come to pass one day that a rack of test tubes replaces the microprocessor-based computer for the solution of specialized tasks and perhaps not. In any event, those working in the burgeoning field of DNA computing believe that the continued close collaboration between biologists and computer scientists will yield new insights that cannot yet be imagined.

——
[archive-e:45-v:2000-y:2000-d:2000-11-06-p:./2000/iss45/techno.htm]