Solving some mathematical problems such as NP-complete problems by conventional silicon-based computers is problematic and takes so long time. DNA computing is an alternative method of computing which uses DNA molecules for computing purposes. DNA computers have massive degrees of parallel processing capability. The massive parallel processing characteristic of DNA computers is of particular interest in solving NP-complete and hard combinatorial problems. NP-complete problems such as knapsack problem and other hard combinatorial problems can be easily solved by DNA computers in a very short period of time comparing to conventional silicon-based computers. Sticker-based DNA computing is one of the methods of DNA computing. In this paper, the sticker based DNA computing was used for solving the 0/1 knapsack problem. At first, a biomolecular solution space was constructed by using appropriate DNA memory complexes. Then, by the application of a sticker-based parallel algorithm using biological operations, knapsack problem was resolved in polynomial time. 1. Introduction DNA encodes the genetic information of cellular organisms. The unique and specific structure of DNA makes it one of the favorite candidates for computing purposes. In comparison with conventional silicon-based computers, DNA computers have massive degrees of miniaturization and parallelism. By recent technology, about 1018 DNA molecules can be produced and placed in a medium-sized laboratory test tube. Each of these DNA molecules could act as a small processor. Biological operations such as hybridization, separation, setting, and clearing can be performed simultaneously on all of these DNA strands. Thus, in an in vitro assay, we could handle about 1018 DNA molecules or we can say that 1018 data processors can be executed in parallel. In 1994, Adleman introduced the DNA computing as a new method of parallel computing [1]. Adleman succeeded in solving seven-point Hamiltonian path problem solely by manipulating DNA molecules and suggested that DNA could be used to solve complex mathematical problems. In 1999, a new model of DNA computing (sticker model) was introduced by Roweis et al. [2]. This model has a kind of random access memory that requires no strand extension, uses no enzymes, and its materials are reusable. Sticker-based DNA computing has potential capability for being a universal method in DNA computing. Roweis et al. [2] also proposed specific machine architecture for implementing the sticker model as a microprocessor-controlled parallel robotic workstation. Thus, the operations
References
[1]
L. Adleman, “Molecular computation of solutions to combinatorial problems,” Science, vol. 266, pp. 1021–1024, 1994.
[2]
S. Roweis, E. Winfree, R. Burgoyne et al., “A sticker based model for DNA computation,” in Proceedings of the 2nd Annual Workshop on DNA Computing, Princeton University, L. Landweber and E. Baum, Eds., Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, pp. 1–29, American Mathematical Society, 1999.
[3]
R. J. Lipton, “DNA solution of hard computational problems,” Science, vol. 268, pp. 542–545, 1995.
[4]
L. M. Adleman, On Constructing a Molecular Computer, Department of Computer Science, University of Southern California, 1995.
[5]
L. M. Adleman, “On constructing a molecular computer,” in DNA Based Computers, R. J. Lipton and E. B. Baum, Eds., pp. 1–22, American Mathematical Society, 1996.
[6]
W.-L. Chang and M. Guo, “Solving the dominating-set problem in Adleman-Liptons Model,” in Proceedings of the 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 167–172, Kanazawa, Japan, 2002.
[7]
W.-L. Chang and M. Guo, “Solving the clique problem and the vertex cover problem in Adleman-Lipton’s model,” in IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications, pp. 431–436, Tsukuba, Japan, 2002.
[8]
W.-L. Chang and M. Guo, “Solving NP-complete problem in the Adleman-Lipton Model,” in Proceedings of The International Conference on Computer and Information Technology, pp. 157–162, 2002.
[9]
L. Adleman, P. Rothemund, S. Roweis, and E. Winfree, “On applying molecular computation to the data encryption standard,” in Proceedings of the 2nd DIMACS wWorkshop on DNA Based Computers, Princeton University, pp. 24–48, 1996.
[10]
H. Taghipour, A. Taghipour, M. Rezaei, and H. Esmaili, “Solving the independent set problem by sticker based DNA computers,” American Journal of Molecular Biology, vol. 2, no. 2, pp. 153–158, 2012.
[11]
Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science, vol. 278, no. 5337, pp. 446–449, 1997.
[12]
M. Amos, A. Gibbons, and D. Hodgson, “Error-resistant implementation of DNA computations,” in Proceedings of the 2nd DIMACS Workshop on DNA Based Computers, 1996.
[13]
M. Amos, A. Gibbons, and D. Hodgson, “A new model of DNA computation,” in Proceedings of the 12th British Colloquium on Theoretical Computer Science, 1996.
[14]
M. Hagiya, M. Arita, D. Kiga, K. Sakamoto, and S. Yokoyama, “Towards parallel evaluation and learning of boolean μ-formulas with molecules,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 48, pp. 57–72, 1999.
[15]
E. Winfree, “Simulations of computing by self-assembly,” in Proceedings of the 4th International Meeting on DNA Based Computers, pp. 213–239, 1998.
[16]
E. Winfree, F. Liu, L. A. Wenzler, and N. C. Seeman, “Design and self-assembly of two-dimensional DNA crystals,” Nature, vol. 394, no. 6693, pp. 539–544, 1998.
[17]
E. Winfree, X. Yang, and N. Seeman, “Universal computation via self-assembly of DNA: some theory and experiments,” in Proceedings of the 2nd DIMACS Workshop on DNA Based Computers, 1996.
[18]
Q. Liu, Z. Guo, A. E. Condon, R. M. Corn, M. G. Lagally, and L. M. Smith, “A surface-based approach to DNA computation,” in Proceedings of the 2nd Annual Meeting on DNA Based Computers, Princeton University, 1996.
[19]
H. Taghipour, M. Rezaei, and H. Esmaili, “Applying surface-based DNA computing for solving the dominating set problem,” American Journal of Molecular Biology, vol. 2, no. 3, pp. 286–290, 2012.
[20]
G. Rozenberg and H. Spaink, “DNA computing by blocking,” Theoretical Computer Science, vol. 292, no. 3, pp. 653–665, 2003.
[21]
M. R. Garey and D. S. Johnson, Computer and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco, Calif, USA, 1979.
