Research Of An Improved Model On DNA Computation

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. Therefore, taking the strategy, method and technology of parallel processing of the traditional computers into DNA computing is an important way to reduce the DNA strands volume.In this paper, we do research on the characteristic of DNA operations deeply, then combine theoretical analysis with biology experiment to modify the unscalable Chang et al.'DNA models. Meanwhile, taking one of the improtant parallel computing technology—divide and conquer in traditional computers into the new model to design new algorithms for subset-sum and SAT problem. The algorithms designed can decrease the DNA strands sharply. The comparison of the proposed algorithm with the past researches show that it is the first DNA algorithm that can solve the subset-sum and SAT problem in O(2n/2) volume, as compared by far the best molecular algorithm for it in which O(2n) DNA strands is used.