Research Article: Solving the 0/1 Knapsack Problem by a Biomolecular DNA Computer

Date Published: February 18, 2013

Publisher: Hindawi Publishing Corporation

Author(s): Hassan Taghipour, Mahdi Rezaei, Heydar Ali Esmaili.


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.

Partial Text

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 this paper, the sticker based DNA computing was used for solving the 0/1 knapsack problem. This method could be used for solving other NP-complete problems. There are four principal operations in sticker model: Combination, Separation, Setting and Clearing. We also defined a new operation called “divide” and applied it in construction of solution space.




Leave a Reply

Your email address will not be published.