Chinese Journal of Computers   Full Text
Title	An O(1.414n) Volume Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing
Authors	LI Ken-Li1),2) YAO Feng-Juan1) XU Jin2) LI Ren-Fa1)
Address	1)(School of Computer and Communication, Hunan University, Changsha 410082) 2)(Institute of Biomolecular Computer, Huazhong University of Science and Technology, Wuhan 430074)
Year	2007
Issue	No.11(1947—1953)
Abstract &   Background	Abstract How to decrease the volumes in DNA computers has become an important research area in DNA computing. It is showed that the poor scalability in the DNA-based algorithms roots in the poor scalability of the DNA models. In this paper, a DNA model for good scalability is proposed. It is based on biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model. The method of fluorescence labeling and the technique of gel electrophoresis are incorporated into the model. Based on it, a new DNA algorithm for solution of the subset-sum problem is proposed where the strategy of divide and conquer and a new designed algorithm of ParallelSearcher are introduced. The proposed algorithm can solve the n-dimension subset-sum instances 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 that can be theoretically broken using the present biological technology may be enlarged from 60 to 120 variables. keywords DNA-based computing; subset-sum problem; divide and conquer; parallel processing; NP-complete problem background This research is supported by the key Project of National Natural Science Foundation of China under grant No.60533010, the Projects of National Natural Science Foundation of China under grants (60603053, 60403002): Research on a scalable DNA computer model, the Theory, Model and Method of DNA Computer etc. The projects mainly focus on DNA computer models for processing graphical messages, including encoding DNA sequences, synthesizing DNA molecules, setting up the model, detecting solutions, etc. The research group has been working on many aspects of DNA computing since 1996 and have published a monograph and more than 120 papers on DNA computing and DNA computer. This paper uses the basic strategy for devising parallel algorithm—Divide and conquer to design a proposed DNA model of subset-sum problem for avoidance of the limitation of enumeration in subset-sum problem.