10. APPLICATIONS OF DNA COMPUTER :

10. APPLICATIONS OF DNA COMPUTER :

10.1) Massively Parallel Processing:

The primary advantage offered by most proposed models of DNA based computation is the ability to handle millions of operations in parallel. The massively parallel processing capabilities of DNA computers may give them the potential to find tractable solutions to otherwise intractable problems, as well as potentially speeding up large, but otherwise solvable, polynomial time problems requiring relatively few operations. The use of DNA to perform massive searching and related algorithms will be referred to as "classic" DNA computation for the purposes of this discussion.

Proposed "classical" models of DNA computers derive their potential advantage over conventional computers from their ability to:

➢ Perform millions of operations simultaneously;
➢ Generate a complete set of potential solutions;
➢ Conduct large parallel searches; and
➢ Efficiently handle massive amounts of working memory.

These models also have some of the following drawbacks :

➢ Each stage of parallel operations requires time measured in hours or days, with extensive human or mechanical intervention between steps;
➢ Generating solution sets, even for some relatively simple problems, may require impractically large amounts of memory; and
➢ Many empirical uncertainties, including those involving: actual error rates, the generation of optimal encoding techniques, and the ability to perform necessary bio-operations conveniently in vitro or in vivo.

With these qualities in mind, the comparison between conventional computing and "classic" DNA computation comes down to one of depth versus breadth. A working DNA based computer might hold an advantage over conventional computers when applied to decomposable problems, those problems that are able to be divided into separate, non-sequential tasks, because they can hold so much data in memory and conduct so many operations at once. However, due to the length of time required to conduct the biochemical operations, non-decomposable problems, those requiring many sequential operations, are likely to remain much more efficient on a conventional computer. [2]

Within the paradigm of "classic" DNA computation there exists many different models, each with different advantages and degrees of applicability to classes of problems. An example of one model differing from Adleman's original search algorithm is the surface-based DNA algorithm used to solve the minimal set cover problem in [8]. This technique proposes to decrease the potential for error from lost DNA strands by affixing them to a surface of glass or silicon. The efficiency of their algorithm is dependent on the method of encoding quantity by strand length so the authors have speculated that such a model might be inappropriate for application to problems where the validity of a solution is not proportional to its size. A surface-based approach to DNA computation was also considered in [13], which suggests the products of bit operations could be identified using optical readers scanning for the relative surface position of hybrid double strands consisting of a previously unknown bitstring and a value being held by that bit. The ability to read output in this manner may drastically increase the feasibility of implementing a DNA computer outside the conventional laboratory setting. It might also encourage the development of DNA/Electronic computer hybrids, with different problem types being handled by different components, and the electronic portion conveying the output to the user. Another model [10] makes use of 3-Dimensional DNA structures to reduce errors and necessary steps. This method of using the structral properties of DNA may also lead to more efficient storage mechanisms.

Classical DNA computing techniques have already been theoretically applied to a real life problem: breaking the Data Encryption Standard (DES). Although this problem has already been solved using conventional techniques in a much shorter time than proposed by the DNA methods, the DNA models are much more flexible, potent, and sender of cost effective.

DES is a method of encrypting 64-bit messages with a 56-bit key, used extensively in the United States. Electronic keys are normally a string of data used to code and/or decode sensitive messages. By finding the appropriate key to a set of encrypted messages, one can either read encoded messages or pose as the such messages. Using a special purpose electronic computer and differential cryptanalysis, it has been shown that the key to DES can be found in several days. However, to do so would require 2^43 examples of corresponding encrypted and unencrypted messages (known as plain-text/cipher-text pairs) and would slow down by a factor of 256 if the strength of the encrypting key was increased to 64-bits. In [6] it is proposed that DES could be broken using a DNA based computer and a search algorithm similar to Adleman's original technique. This procedure would be expected to take 4 months, but would only need a single plain-text/cipher-text pair or an example of cipher text with several plain text candidates to be successful. The feasibility of applying DNA computation to this problem was also addressed in [3] using a more refined algorithm (the sticker model approach) which enabled the researchers to suggest that they could solve the problem using less than a gram of DNA, an amount that could presumably be handled by a desk top sized machine. Both models would likely be more cost and energy effective than the expensive electronic processors required by conventional means, but are entirely theoretical. The first model ignores error rates incurred though laboratory techniques and the inherent properties of the DNA being used. The second model requires an error rate approaching .0001, with higher rates substantially affecting the volume of DNA required. Despite these assumptions, these models show that existing methods of DNA computation could be used to solve a real life problem in a way that is both practical and superior to methods used by conventional computers. In [3] it is also demonstrated that such benefits can be obtained despite error rates that would be unacceptable in an electronic computer and that may be unavoidable in a molecular one.