%0 Journal Article
%T Solving the 0/1 Knapsack Problem by a Biomolecular DNA Computer
%A Hassan Taghipour
%A Mahdi Rezaei
%A Heydar Ali Esmaili
%J Advances in Bioinformatics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/341419
%X 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
%U http://www.hindawi.com/journals/abi/2013/341419/