DNA Computing Based Research On Two Special Category Of Application Problems

The ability of DNA computers affords a number of useful properties such as massive parallelism and a huge memory capacity, which makes DNA computing becomes one of the possible ways to solve NP complete and other hard problems. For one hand, most task scheduling problems are NP hard problems, and without coresponding DNA parallel algorithms. For another hand, 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 method of parallel processing in computers into DNA computing is an important way to reduce the DNA strands volume.In this paper, we take the Chang's model which uses the sticker's solution space and Adleman's DNA operation set into the independent multiply processors task scheduling problems and design an DNA parallel algorithm. Meanwhile, we also use the plamist model into solving the knapsack problems, and take one of the improtant parallel computing technology—divide and conquer in traditional computers into the new model to design new algorithms for knapscak problem. The algorithms designed can decrease the DNA strands sharply from O(2n/2) volume into O(2n) DNA strands.