Research On DNA-base Algorithms Of Subset-product Problem

Since Adleman successfullu solved an instance of hamiltonian path problem with 7 vertexes, which is a NP-complete problem, biomolecular computation has become a new a research field which sets up a bridge over computer science and biology.With the researching goes deeply, the problem of exploding of solution space existing in DNA computing algorithms based on the exhaust method, this has been the bottleneck in the application of DNA computing. How to decrease the volume in DNA computers has become a basic problem in the research of DNA computing. And the poor scalability in the DNA-based algorithms roots in the poor scalability of the DNA models. 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.This paper proposed an improved plasmid model for DNA computing. For the objective to decrease the DNA volume which increases in a pure exponentially with the scale of the subset sum problem, an improved plasmid model is proposed in this paper. Based on it, a new DNA algorithm for subset sum problem is also proposed where the strategy of divide and conquer is introduced. In this algorithm, we develop an improved plasmid-based algorithm to finish the function of decimal subtraction. The proposed algorithm can solve the n-dimension subset sum 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. Therefore, the scale of the public key cryptosystem can be theoretically broken using biological operations may be enlarged from 60 to 120 variables.