Research And Application Of An Scalable Model On DNA Computing

The computer technique is considered as one of the three big revolutions of science in 20 centuries, and the computer plays a great role for the development of society. But quantum physics successfully forecast the increase of micro-processing ability of chip cannot keep down for a long period. So, scientists are seeking other completely new computerst ructure.Such as artificial neural network computer, quantum computer, optical computer as well as DNA computer model. Among them, the DNA computer is paid much attention by scientist in the laterer years.The ability of DNA computers to perform calculations using specific biochemical reactions, affords a number of useful properties such as massive parallelism and a huge memory capacity, which can overcome the storage and computing speed problem in traditional compters. Therefore, DNA computing becomes one of the possible ways to solve NP complete and other hard problems. However, different from the traditional computers, DNA computers are less universal than traditional ones, so the algorithm or a DNA computer just for one problem can not be used for other problems without any modification. This leads to almost all the current DNA computing algorithms taking the brute-force mehod regardless of the different models, and the exponential increase in DNA volume.In this paper, reducing the the volume in DNA computing is the main line. Therefore, taking the strategy, method and technology of parallel processing of the traditional computers into DNA computing is an important way. Regarding the algorithm design, we mainly present three volume efficient algorithms for the folowing three problems: the 3-coloring problem, the maximum clique problem and the partition problem. Firstly, The improtant parallel computing technology - pruning strategy is taken into the design of the new models of the 3-coloring problem and the maximum clique problem. The algorithms designed can decrease the DNA strands sharply. The comparison of the proposed algorithm with the past researches show that it can solve the 3-coloring problem in O(2n) volume, as compared by far the practicable molecular algorithm for it in which O(3n) DNA strands is used , and the maximum number of DNA strands required was O( 3 n). Secondly, divide and conquer in traditional computers is introduced into the new model to design new algorithm for partition problem. The proposed algorithm can solve the partition problem by using the O(1.414n) shorter DNA strands on the condition of not varying the time complexity, as compared by far the best molecular algorithm for it in which O(2n) DNA strands is used. The three new algorithms are highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard maximum clique problems.