Solving the 0-1 knapsack problem based on a parallel intelligent molecular computing model system

Abstract

The 0-1 knapsack problem is one of the classical NP-hard problems and has been one of the hot research topics in the last few decades. It offers many practical applications in optimization and applied mathematics, such as project selection, resource distribution, investment decision-making and so on. Simultaneity in previous studies DNA molecular computation usually be used to solve NP-complete continuous path search problems (for example HPP, traveling salesman problem), rarely for NP problems with discrete solutions result, such as the 0-1 knapsack problem, graph coloring problem. In this paper, we present a new algorithm for solving the 0-1 knapsack problem with DNA molecular operations. For 0-1 knapsack problem with n distinct items, weight capacity C and total profits W, we reasonably design fixed length DNA strands representing items, take appropriate steps and get the solutions of the problem in proper length range using O(n + C + W) time. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation.

Keywords

DNA biological computing the 0-1 knapsack problem Adleman-Lipton model NP-complete problem

1 Introduction

DNA biological computing is a newly emerging crossdisciplinenary science that uses DNA molecular biotechnologies to solve conundrum problems of computer science and computational mathematics. DNA computing can execute billions of operations simultaneously. The massive parallelism of DNA computing comes from the large number of molecules which chemically interact in a small volume. DNA also provides a huge storage capacity since they encode information on the molecular scale. Meanwhile DNA has a great application prospect for having wide range of abundant resources. NP (nondeterministic polynomial time) problems are a class of mathematical problems which have most likely exponential complexity, for which no efficient solution has been found yet [1]. DNA computing has the advantages of parallel computing, huge storage capacity and low energy consumption. Adleman [2], Liption [3] and Sanches [41] had proved that DNA computing can solve complex NP problems with polynomial time complexity, comparing to exponential complexity of other classical algorithms [43]. As the pioneering work for DNA computing, Adleman [2] presented an idea of solving the Hamiltonian path problem of size n in O(n) steps using DNA molecules. Lipton [3] demonstrated that Adleman’s experiment could be used to figure out the NP-complete satisfiability problem. In recent years, lots of papers have occurred for designing DNA procedures and algorithms to solve various NP-complete problems [4 –30]. However, most of the previous works in DNA computing are concentrated on solving the path search problems that the optimum results are continuous head-to-tail ligation edges or vertices sets. For example, Lee [11] first designs different length’s strands representing paths values and cities, takes molecular operations to generate strands standing for all possible paths, then uses biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel, to get the optimum solutions of the traveling salesman problem. To solve the shortest path problem, Narayanan [12] respectively carries out DNA reaction to get the strands for a list of series paths, chooses the shortest length strands as the solution through DNA biotechnologies. The previous researches have some insufficient factors. One is that the strands for the possible paths are usually very long, while too long DNA strands can lead to error-prone in annealing and separation procedures using modern biotechniques. The other is that previous research problems are optimum path search ones, so that the possible solutions can be relatively easily represented by DNA strands, while the 0-1 knapsack problem is a discrete mathematics problem with discontinuous solutions. So representation of discrete data with DNA strands is an important issue toward expanding the capability of DNA computing to solve many optimization problems.

The 0-1 knapsack problem is a problem of central importance in optimization and computational sciences. The 0-1 knapsack problem is NP-hard [13], and it is considered unlikely to have an efficient algorithm for solving it up to now. Zou [36], with the aid of two important operations: position updating and genetic mutation with a small probability, proposes a novel global harmony search algorithm to solve 0-1 knapsack problems. Captivo [37] examines the performances of a new labeling algorithm to 4nd all the efficient paths of the bicriteria 0-1 knapsack problem. Zhang [38] introduced an amoeboid organism model to solve the problem. It has three steps: First, the 0-1 knapsack problem is converted into a directed graph by the network converting algorithm. Then, for the purpose of using the amoeboid organism model, the longest path problem is transformed into the shortest path problem. Finally, the shortest path problem can be well handled by the amoeboid organism algorithm. There are n different items available and each item i has a weight wi and a profit pi. The knapsack can hold weight sum at most C. The problem is to find an optimal set of items so as to maximize the total profits subject to the knapsacks weight capacity. The profits, weights, and capacities are positive integers. Let xi (1 ≤ i ≤ n) be binary variables given as follows: $x_{i} = {\begin{matrix} 0 & if item i is not selected \\ 1 & if item i is selected \end{matrix}$

The 0-1 knapsack problem can be mathematically formulated as follows: $\begin{matrix} Max \sum_{i = 1}^{n} p_{i} x_{i} \\ s . t . \sum_{i = 1}^{n} w_{i} x_{i} \leq C i = 1, 2, \dots, n \end{matrix}$

The binary decision variables xi are used to indicate whether item i is included in the knapsack or not. For instance, eg. 1 is as: $\begin{matrix} x = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}, x_{i} = 0 or 1, \\ C = 10, w = {2, 2, 6, 5, 4}, p = {6, 3, 5, 4, 6} \end{matrix}$ defines such a problem. It is not difficult to find that the items set ${x_{1}, x_{2}, x_{3}, x_{4}, x_{5}} = {1, 1, 0, 0, 1} .$ with profit 15 is the solutions to the 0-1 knapsack problem for eg. 1.

The rest of this paper is organized as follows. In Section 2, the Adleman-Lipton model is introduced in detail. Section 3 uses a DNA molecular algorithm for solving the 0-1 knapsack problem and the complexity of the proposed algorithm is described in Section 4. We get conclusions in Section 5.

2 The Adleman-Lipton model

DNA molecular computers work at the molecular level. Because biological and mathematical operations have some similarities, DNA, the genetic material that encodes for living organisms, is stable and predictable in its reactions and can be used to encode information for mathematical systems.

DNA is the major information storage molecule in living cells, and billions of years of evolution have tested and refined both this wonderful informational molecule and highly special enzymes that can either duplicate the information in DNA molecules or transmit this information to other DNA molecules.

A DNA (deoxyribonucleic acid) is a polymer, which is strung together from monomers called deoxyribonucleotides [14]. Distinct nucleotides are detected only with their bases. Those bases are, respectively, abbreviated as adenine (A), guanine (G), cytosine (C), and thymine (T). Two strands of DNA can form (under appropriate conditions) a double strand, if the respective bases are the Watson-Crick complements of each other: A matches T and C matches G; also 3^′end matches 5^′ end, e.g., the singled strands 5^′CTGCAGTACACC3^′ and 3^′GACGTCATGTGG5^′ can form a double strand. We also call the strand 3^′GACGTCATGTGG5^′ as the complementary strand of 5^′CTGCAGTACACC3^′. The length of a single stranded DNA is the number of nucleotides comprising the single strand. Thus, if a single stranded DNA includes 20 nucleotides, it is called a 20mer.

The DNA operations proposed by Aldeman [2] and Lipton [3] are described below. These operations will be used for figuring out solutions of the unbalanced assignment problem in this paper. In the Adleman-Lipton model: a tube is a set of molecules of DNA. Given a tube, we can perform the following operations [31 –33]:

Merge (T₁, T₂): for two given test tubes T₁ and T₂, it stores the union T₁ ∪ T₂ in T₁ and leaves T₂ empty;

Copy (T₁, T₂): for a given test tube T₁, it produces a test tube T₂ with the same contents as T₁;

Detect (T): given a test tube T, it outputs “yes” if T contains at least one strand, otherwise, outputs “no”;

Separation (T₁, X, T₂): for a given test tube T₁ and a given set of strings X, it removes all single strands containing a string in X from T₁, and produces a test tube T₂ with the removed strands;

Selection (T₁, L, T₂): for a given test tube T₁ and a given integer L, it removes all strands with length L from T₁, and produces a test tube T₂ with the removed strands;

Sort (T₁, T₂, T₃): for a given test tube T₁, it choose the shortest length strands in the tube T₂, the longest strands in T₃ and the remaining strands in T₁;

Annealing (T): for a given test tube T, it produces all feasible double strands in T. The produced double strands are still stored in T after annealing;

Denaturation (T): for a given test tube T, it dissociates each double strand in T into two single strands;

Ligation (T): for a given tube T, the operation is used to ligate together the strands in T;

Discard (T): for a given test tube T, it discards the tube T;

Read (T): for a given tube T, the operation is used to describe a single molecule, which is contained in the tube T. Even if T contains many different molecules each encoding a different set of bases, the operation can give an explicit description of exactly one of them;

Append-tail (T, z): for a given test tube T and a given DNA singled strand zit appends z onto the end of every strand in the tube T.

Since these twelve manipulations are implemented with a constant number of biological steps for DNA strands [34 , 40– 42], we assume that each manipulation is in O(1) time complexity.

3 DNA algorithm for the 0-1 knapsack problem

3.1 Thinking process

In the following, the symbols #, $\bar{#}$ , 0, 1, A_k, B_k (k = 1,2, ... , n) denote distinct DNA singled strands with same length, say t-mer (t can choose a small integer). Obviously, the length of the DNA singled strands greatly depends on the size of the problem involved in order to distinguish all above symbols and to avoid hairpin formation [15]. Then in the below operations, we use the distinct DNA singled strands symbols A_k0B_k, A_k1B_k (k = 1,2, ... , n) to denote the item x_k, with A_k1B_k for x_k including in the knapsack, while A_k0B_k for not. Simultaneity the symbol # and $\bar{#}$ are the signals of division between different solution strands. For distinguishing whether some items combination satisfying the weight constraint or not, we meantime design DNA string X with 1-mer length. We denote DNA singled strands Y_k with length of ||p_k||-mer to choose the optimum items combination. Let $\begin{matrix} P & = & {0, 1, # A_{1}, B_{n} #, B_{k - 1} A_{k} | k = 2, 3, \dots, n}, \\ Q & = & {\bar{#}, \bar{A_{k} 1 B_{k}}, \bar{A_{k} 0 B_{k}} | k = 1, 2, 3, \dots, n}, \\ R & = & {Y_{k} | 1 \leq k \leq n, | | Y_{k} | | = p_{k}}, \\ S & = & {c_{k} | 1 \leq k \leq n, | | c_{k} | | = w_{k}}, \\ T & = & {X} . \end{matrix}$

3.2 Detailed DNA algorithm

For a graph with n items, every possible subset of the items {x₁, x₂, …, x_n} can be expressed by a n-digit binary number. A bit set to 1 represents the item in the subset, while a bit set to 0 represents the item out of the subset. For example, in eg. 1, the items subset {x₂, x₄, x₅} can be expressed by the binary number 01011. In this way, we transform all possible subsets in a n-item knapsack problem into an ensemble of all n-digit binary numbers. We call this as datapool.

(1) We choose all possible subsets of items.

(1-1) Merge (P,Q);

(1-2) Aneealing (P);

(1-3) Ligation (P);

(1-4) Denaturation (P);

(1-5) Separation (P, {# A₁}, T₁);

(1-6) Discard (P);

(1-7) Separation (T₁, {B_n #}, P).

After the above seven steps of manipulations, the singled strands in tube P will encode all possible subsets of items. For example, in eg. 1, we have singled strands: $# A_{1} 1 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 1 B_{4} A_{5} 0 B_{5} # \in P .$

They denote the subset of items {x₁, x₂, x₄} corresponding to the binary number 11010. This operation can be finished in O(1) steps since each manipulation above works in O(1) steps.

(2) Each singled strand in tube P denotes one possible item subset after step (1). However the 0-1 knapsack problem requires that the sum of weight is not more than the given capacity C. If x_i is selected in a subset, we should append the strands c_i at the end of previous strands. For example, in eg. 1, the singled strands # A₁1B₁A₂0B₂A₃0B₃A₄1B₄A₅1B₅ # (representing the subset of items {x₁, x₄, x₅}) should be appended with stands c₁, c₄, c₅. Only so, we could choose all eligible items subsets in the next step.

For k = 1 to k = n

(2-1) Separation (P, {A_i1B_i}, T₂);

(2-2) Append (T₂, c_i);

(2-3) Merge (P, T₂);

(2-4) Discard (T₂).

End for

After the above operations, the singled strands in tube P are all possible items subsets with denoting weight stands. Meanwhile we use one “For” clauses, thus this step can be finished in O(n) steps since each single manipulation above works in O(1) steps.

(3) The solution of 0-1 knapsack problem should be a items subset which satisfies the sum of weight is not more than given capacity C. So we should check all the items subsets whether to satisfy the above restrictive conditions. At the same time, in order not to affect the profits measurement, we should make the eligible strands at the same length before the next step. This is done by the following operations:

For i = 1 to i = C

(3-1) Selection (P, (3n + 2)t + i,T₃);

(3-2) If (Detect (T₃) = “Yes”)

Then (3-3) to (3-5)

(3-3) Append (T₃, X);

(3-4) Merge ( P,T₃);

(3-5) Discard (T₃);

End for

(3-6) Selection (P, (3n + 2)t + C,T₄);

(3-7) Discard (P);

(3-8) Copy (T₄, P);

For the eg. 1, the singled strands $# A_{1} 1 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 0 B_{4} A_{5} 1 B_{5} # c_{1} c_{2} c_{5} \in P$ represent containing the items subset {x₁, x₂, x₅} with the weight sum 8, so we append strand X two (C-w₁-w₂-w₅ = 10-8 = 2) times at end of previous strands to $# A_{1} 1 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 0 B_{4} A_{5} 1 B_{5} # c_{1} c_{2} c_{5} XX .$

In the above operation, we use one “For” clause, thus this operation can be executed in O(C) steps since each single manipulation above works in O(1) steps.

(4) The 0-1 knapsack problem is to find an optimal subset of items so as to maximize the total profits subject with the knapsacks weight capacity restriction. In order to denote the total profits of the items subsets, we append strands Yi at the end of strands if xi is selected in the subset. Taking the eg. 1 for example, the singled strands in P $# A_{1} 0 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 1 B_{4} A_{5} 0 B_{5} # c_{2} c_{4} XXX$ stranding for items subset {x₂, x₄}, we append strands Y₂ and Y₄ at the end of the previous strands to $# A_{1} 0 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 1 B_{4} A_{5} 0 B_{5} # c_{2} c_{4} XXX Y_{2} Y_{4}$

This is done by the following manipulations:

For i = 1 to i = n

(4-1) Separation (P, {A_i1B_i}, T₅);

(4-2) Append (T₅, Y_i);

(4-3) Merge (P,T₅);

(4-4) Discard (T₅).

End for

In the above operations, we use one “For” clause, thus this operation can be finished in O(n) steps since each single manipulation above works in O(1) steps.

(5) We take out the singled strands in P with maximum length, which represent the solutions of 0-1 knapsack problem. For example, in eg. 1, the singled strands in P with maximum length are $\begin{matrix} # A_{1} 1 B_{1} A_{2} 1 B_{2} A_{3} 0 B_{3} A_{4} 0 B_{4} A_{5} 1 B_{5} # c_{1} c_{2} \\ c_{5} XX Y_{1} Y_{2} Y_{5} . \end{matrix}$

Therefore, solutions of 0-1 knapsack problem for the eg. 1 are {x₁, x₂, x₅} with the profits sum 15. We choose the maximum length items subset from all eligible subsets.

For i = W to i = 1

(5-1) Selection (P, (3n + 2)t + C + i, T6);

(5-2) If (Detect (T6) = “Yes”)

Break;

End for

In the above operation, W is all items profit sum. We use one “For” clause, the worst conditions is that the algorithm stop at i = 1, thus this operation can be finished less than O(W) steps since each single manipulation above works in O(1) steps. In the above operation, this operation can be finished in O(1) time steps since each single manipulation above works in O(1) steps. Finally the “Read” operation is applied to giving the final solutions to the unbalanced assignment problem.

(6) Finally the “Read” operation is used to get the exact solutions of the 0-1 knapsack problem. For example, for the eg. 1, the maximum profits items subset is {x₁, x₂, x₅}. This operation works in O(1) steps.

(6-1) Read (T₆).

4 The complexity and feasibility of the proposed DNA algorithm

The following theorems prove that the algorithm proposed above really can get solutions of the 0-1 knapsack problem in O(n+C+W) steps using DNA molecules operation.

Theorem 1.The solutions of 0-1 knapsack problem with n items, weight sum restriction C and profits sum W can be solved by the DNA computing algorithm.

Proof. The basic idea of our DNA algorithm for the 0-1 knapsack problem is as listed processes: get whole possible allocation by ruling out illegal segments from all possible allocation data pool, then, identify and get the solutions of the 0-1 knapsack problem by corresponding DNA operations. Concretely, the proposed algorithm consists of six steps.

Step 1. Construct set T of all possible 2ⁿ solutions for the 0-1 knapsack problem;

Step 2. For all possible solutions, append the capacity weight strands c_i at the end corresponding strands;

Step 3. The solution strands, over given capacity C, will be eliminated;

Step 4. In order to denote the total profits of the items subsets, we append profit strands Y_i at the end of strands if x_i is selected in the subset;

Step 5. Evaluate the total profits of possible strands and get the optimal solution strands to the 0-1 knapsack problem;

Step 6. Pick out remains in T₆ and get the solutions.

Theorem 2.The solutions of 0-1 knapsack problem with n items, weight sum restriction C and profits sum W can be figured out in O(n+C+W) steps by means of DNA molecules parallel supercomputing.

Proof. After the operations of Step (1), all the singled strands in tube P denote all possible subsets of items. Then the strands can be described: $\begin{matrix} # A_{1} z_{1} B_{1} A_{2} z_{2} B_{2} \dots A_{k} z_{k} B_{k} \dots A_{n} z_{n} B_{n} # \\ z_{k} = 0 or 1 . \end{matrix}$

After the operations of second step, all the strands in P denoting possible items subset will be appended weight strands to satisfy weight sum restriction. Then the strands can be described: $\begin{matrix} # A_{1} z_{1} B_{1} A_{2} z_{2} B_{2} \dots A_{1} z_{1} B_{k} \dots A_{n} z_{n} B_{n} # c_{i_{1}} c_{i_{2}} \dots \\ c_{i_{m}} z_{k} = 0 or 1 : \\ | | c_{i_{k}} | | = w_{i_{k}} if z_{ik} = 1 . \end{matrix}$

We find the strands satisfying the sum weight restriction at the third step. Simultaneity in order not to affect the profits measurement at the fourth step, we make the eligible strands keep the same length by append strands X $(C - \sum_{k = 1}^{m} ∥ w_{i_{k}} ∥)$ times at the previous strands. In the first instance we reasonably design the length of #, A_k, B_k, 0, 1, c_i, Y_i and X, For $\begin{matrix} | | A_{k} | | = | | B_{k} | | = | | # | | = | | 0 | | = | | 1 | | = | | z_{k} | | = t, \\ | | c_{k} | | = w_{k}; | | Y_{k} | | = p_{k}; | | X | | = 1 . \end{matrix}$

So we define S as the strands after the Step (4). Then S can be described: $\begin{matrix} # A_{1} z_{1} B_{1} A_{2} z_{2} B_{2} \dots A_{k} z_{k} B_{k} \dots A_{n} z_{n} B_{n} # c_{i_{1}} c_{i_{2}} \dots \\ c_{i_{m}} X X \dots X . \end{matrix}$

The number of appending X times is decided by the existing items weight information on the strands. Due to we get the eligible items set strands satisfying the weight sum restriction at the same length, so we append the profits information strands at end of previous strands as so to get the optimal result strands. Then the strands can be described: $\begin{matrix} # A_{1} z_{1} B_{1} A_{2} z_{2} B_{2} \dots A_{k} z_{k} B_{k} \dots A_{n} z_{n} B_{n} # c_{i_{1}} c_{i_{2}} \\ \dots c_{i_{m}} X X \dots {XY}_{i_{1}} Y_{i_{2}} \dots Y_{i_{m}} . \end{matrix}$

We reasonably design the length $| | Y_{k} | | = p_{k}, \sum_{k = 1}^{m} ∥ Y_{i_{k}} ∥$ mean the profits sum of the eligible subsets. Then the length L of strands can be described: $\begin{matrix} ∥ L ∥ & = & ∥ # ∥ + ∥ A_{1} ∥ + ∥ z_{1} ∥ + ∥ B_{1} ∥ + ∥ A_{2} ∥ \\ + ∥ z_{2} ∥ + ∥ B_{2} ∥ + \dots + ∥ A_{n} ∥ + ∥ z_{n} ∥ \\ + ∥ B_{n} ∥ + ∥ # ∥ + ∥ c_{1} ∥ + ∥ c_{2} ∥ + \dots \\ + ∥ c_{m} ∥ + ∥ X ∥ + ∥ X ∥ + \dots + ∥ X ∥ \\ + ∥ Y_{i_{1}} ∥ + \dots + ∥ Y_{i_{m}} ∥ \\ = & 2 ∥ # ∥ + \sum_{k = 1}^{n} ∥ A_{k} ∥ + \sum_{k = 1}^{n} ∥ z_{k} ∥ + \sum_{k = 1}^{n} ∥ B_{k} ∥ \\ + \sum_{k = 1}^{m} ∥ w_{i_{k}} ∥ + (C - \sum_{k = 1}^{m} ∥ w_{i_{k}} ∥) ∥ X ∥ \\ + \sum_{k = 1}^{m} ∥ p_{i_{k}} ∥ \end{matrix}$ $\begin{matrix} ∵ 1 \leq \sum_{k = 1}^{m} ∥ p_{i_{k}} ∥ \leq W \\ ∴ (3 n + 2) t + C + 1 \leq ∥ S ∥ \leq (3 n + 2) t + C + W \end{matrix}$

So the length of strands which denote containing eligible items information must be between (3n+2)t+C+1 and (3n+2)t+C+W. The maximal length strands is the solution of the 0-1 knapsack problem. Then we can get the solution in Step (6) in appropriate length range.

Theorem 3.The solutions of the 0-1 knapsack problem can be figured out in O(n+C+W) time complexity by means of DNA molecules parallel supercomputing.

Proof. As the algorithm operations, implemented by basic biological response using DNA strands, are in O(1) time computational complexity [34 , 40– 42], the manipulates of algorithm can be entirely finished in finite operations. $\begin{matrix} O (step (1)) = O (7) = O (1); \\ O (step (2)) = O (4 n) = O (n); \\ O (step (3)) = O (8 C) = O (C); \\ O (step (4)) = O (4 n) = O (n); \\ O (step (5)) = O (2 W) = O (W); \\ O (step (6)) = O (1); \end{matrix}$

So the total time complexity T is as: $\begin{matrix} T & = & O (step (1)) + O (step (2)) + O (step (3)) \\ + O (step (4)) + O (step (5)) + O (step (6)) \\ = & O (1) + O (n) + O (C) + O (n) \\ + O (W) + O (1) = O (n + C + W) \end{matrix}$

In conclusion, we can get the solution of 0-1 knapsack problem with n items in O(n + C+W) time complexity.

5 Conclusions

In this paper, we present DNA algorithms for solving the 0-1 knapsack problem based on biological operations in the Adleman-Lipton model. The proposed algorithms have two advantages. Firstly, the proposed algorithm actually has a lower rate of errors for hybridization because we generate fixed reasonable DNA sequences for generating the solutions of the problem. Secondly, the proposed algorithms can works in O(n+C+W) steps for the 0-1 knapsack problem with n items, Comparing exponential level time by electronic computer. Correspondingly, Azad M A K [39] use a binary version of the artificial fish swarm algorithm to solve the problem with O(nˆ2) to O(mn+nˆ2); Gao [40] presented a quantum-inspired artificial immune system with O(mnˆ2). With the increasing in the scale of the problem, our proposed DNA computing algorithm has more advantages in operational efficiency compared to other algorithms. In addition, huge storage capacity and low energy consumption of reaction are obvious characteristics of our proposed algorithm. All our results in this paper are based on a theoretical model. However, the ability to perform complex operations in solution might help us learn more about the nature of computation and lead to the development of better DNA based computation, capable of solving a wide range of complex problems.

6 Copyright

Authors submitting a manuscript do so in the understanding that they have read and agreed to the terms of the IOS Press Author Copyright Agreement posted in the ‘Authors Corner’ on www.iospress.nl.

6.1 Quoting from other publications

An author, when quoting from someone else’s work or when considering reproducing figures or tables from a book or journal article, should make sure that he/she is not infringing a copyright. Although in general an author may quote from other published works, he should obtain permission from the holder of the copyright if he wishes to make substantial extracts or to reproduce tables, plates or other figures. If the copyright holder is not the author of the quoted or reproduced material, it is recommended that the permission of the author should also be sought. Material in unpublished letters and manuscripts is also protected and must not be published unless permission has been obtained. Submission of a paper will be interpreted as a statement that the author has obtained all the necessary permission. A suitable acknowledgement of any borrowed material must always be made.

Footnotes

Acknowledgments

It was supported by the Open Research Fund of State Key Laboratory of Simulation and Regulation of Water Cycle in River Basin, China Institute of Water Resources and Hydropower Research (Grant Nos. IWHR-SKL-201606, 2016TS07, 2016CG04) National Key Research and Development Program of China (grant No. 2017YFC0405501), and the Research and Development Projects on Application Technology of Heilongjiang Province(GZ16B011). The project was financially supported by Natural Science Foundation of Zhejiang Fund Project (Grant Nos. LY13H180012, LY15B070011), National Natural Science Foundation of China (Grant Nos. 21207103, 11501359 and 11601324) and Scientific Project of Wenzhou (Grant Nos. G20110004, C20150007). The project was also financially supported by the Education Department of Guizhou province science and technology talents support programs (KJH KY[2016]088). The project was also supported by National Natural Science Foundation of China (Grant No. 41671431).

References

Garey

M.R.

and Johnson

D.S.

, Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, 1979.

Adleman

L.M.

, Molecular computation of solution to combinatorial problems, Science266 (1994), 1021–1024.

Lipton

R.J.

, DNA solution of HARD computational problems, Science268 (1995), 542–545.

Roweis

, Winfree

, Burgoyne

, Chelyapov

N.V.

, Goodman

M.F.

, Rothemund

P.W.K.

and Adleman

L.M.

, A sticker based model for DNA computation, Journal of Computational Biology5 (1998), 615–629.

Ouyang

, Kaplan

P.D.

, Liu

and Libchaber

, DNA solution of the maximal clique problem, Science278 (1997), 446–449.

Winfree

, Liu

, Wenzler

L.A.

and Seeman

N.C.

, Design and self-assembly of two dimensional DNA crystals, Nature394 (1998), 539–544.

Sakamoto

, Gouzu

, Komiya

, Kiga

, Yokoyama

, Yokomori

and Hagiya

, Molecular computation by DNA hairpin formation, Science288 (2000), 1223–1226.

Smith

L.M.

, Corn

R.M.

, Condon

A.E.

, Lagally

M.G.

, Frutos

A.G.

, Liu

and Thiel

A.J.

, A surface-based approach to DNA computation, Journal of Computational Biology5 (1998), 255–267.

W.X.

, Xiao

D.M.

and He

, DNA ternary addition, Applies Mathematics and Computation182 (2006), 977–986.

10.

Xiao

D.M.

, Li

W.X.

, Yu

, Zhang

X.D.

, Zhang

Z.Z.

and He

, Procedures for a dynamical system on {0,1}ⁿ with DNA molecules, BioSystems84 (2006), 207–216.

11.

Wang

X.L.

, Bao

Z.M.

, Hu

J.J.

, Wang

and Zhan

, Soling the SAT problem using a DNA computing algorithm based on ligase chain reaction, BioSystems91 (2008), 117–125.

12.

Lee

J.Y.

, Shin

S.Y.

, Park

T.H.

and Zhang

B.T.

, Solving traveling salesman problems with DNA molecules encoding numerical values, BioSystems78 (2004), 39–47.

13.

Narayanan

, Zorbalas

, et al., DNA algorithms for computing shortest paths, in: Koza

J.R.

(Ed.), Proceedings of the Genetic Programming, 1998, pp. 718–723.

14.

Chang

W.L.

, Lin

K.W.

, Chen

J.C.

, et al., Molecular solutions of the RSA public-key cryptosystem on a DNA-based computer, Journal of Supercomputing61 (2012), 642–672.

15.

Chang

W.L.

, Ren

T.T.

, Luo

, et al., Quantum algorithms for biomolecular solutions of the satisfiability problem on a quantum machine, IEEE Transactions on Nanobioscience7 (2008), 215–222.

16.

Chang

W.L.

, Fast parallel DNA-based algorithms for molecular computation: The set-partition problem, IEEE Transactions on Nanobioscience6 (2007), 346–353.

17.

Wang

, Huang

, Tan

, et al., A parallel algorithm for solving the n-queens problem based on inspired computational model[J], Biosystems131 (2015), 22–29.

18.

Liu

X.C.

, Yang

X.F.

, Li

S.L.

and Ding

, Solving the minimum bisection problem using a biologically inspired computational model, Theoretical Computer Science411 (2010), 888–896.

19.

Wang

Z.C.

, Zhang

Y.M.

, Zhou

W.H.

and Liu

H.F.

, Solving traveling salesman problem in the Adleman-Lipton model, Applied Mathematics and Computation219 (2012), 2267–2270.

20.

Castellanos-Garzn

J.A.

, Garca

C.A.

, Novais

, et al., A visual analytics framework for cluster analysis of DNA microarray data[J], Expert Systems with Applications40(2) (2013), 758–774.

21.

Garey

M.R.

and Johnson

D.S.

, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company, 1979.

22.

Zimmermann

K.H.

, Ignatova

and Israel

M.P.

, DNA Computing Models, Springer-Verlag, 2008, pp. 146–147.

23.

Wang

, Tan

, Huang

, et al., A biological algorithm to solve the assignment problem based on DNA molecules computation, Applied Mathematics and Computation244 (2014), 183–190.

24.

Yamamura

, Hiroto

and Matoba

, Solutions of shortest path problems by concentration control, Lect Notes Comput Sci2340 (2002), 231–240.

25.

Zhang

, Chu

C.H.

, Chen

, et al., Splice site prediction using support vector machines with a Bayes kernel, Expert Systems with Applications30(1) (2006), 73–81.

26.

Braich

R.S.

, Johnson

, Rothemund

P.W.K.

, Hwang

, Chelyapov

and Adleman

L.M.

, Solution of a satisfiability problem on a gel-based DNA computer, in: Proceedings of the Sixth International Conference on DNA Computation (DNA 2000), Lecture Notes in Computer Science 2054, 2001, pp. 27–42.

27.

Zhang

H.Y.

and Liu

X.Y.

, A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences, Biosystems105 (2011), 73–82.

28.

Darehmiraki

, A new solution for maximal clique problem based sticker model, Biosystems95 (2009), 145–149.

29.

Braich

R.S.

, Johnson

, Rothemund

P.W.K.

, Chelyapov

and Adleman

L.M.

, Solution of a 20-variable 3-SAT problem on a DNA computer, Science296 (2002), 499–502.

30.

Wang

, Huang

, Meng

, et al., A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation, Biosystems114(1) (2013), 1–7.

31.

Ting

C.J.

, Wu

K.C.

and Chou

, Particle swarm optimization algorithm for the berth allocation problem, Expert Systems with Applications41(4) (2014), 1543–1550.

32.

Chang

W.-L.

and Vasilakos

A.V.

, Molecular algorithms of implementing bio-molecular databases on a biological computer, IEEE Transactions on Nanobioscience14(1) (2015), 104–111.

33.

Chang

W.-L.

, Ren

T.-T.

and Feng

, Quantum algorithms and mathematical formulations of bio-molecular solutions of the vertex cover problem in the finite-dimensional hilbert space, IEEE Transactions on Nanobioscience14(1) (2015), 121–128.

34.

Chang

W.-L.

and Vasilakos

A.V.

, Molecular Computing: Towards a Novel Computing Architecture for Complex Problem Solving (Studies in Big Data), Springer, ISBN-13:978-3319051215, ISBN-10:3319051210, 2014.

35.

Xiao

, Li

, Zhang

, et al., Solving maximum cut problems in the Adleman– Lipton model, Biosystems82(3) (2005), 203–207.

36.

Păun

, Rozenberg

and Salomaa

, DNA Computing, SpringerBerlin Heidelberg, 1998.

37.

Zou

, Gao

, Li

, et al., Solving 0-1 knapsack problem by a novel global harmony search algorithm, Applied Soft Computing11(2) (2011), 1556–1564.

38.

Captivo

M.E.

, Clímaco

, Figueira

, et al., Solving bicriteria 0-1 knapsack problems using a labeling algorithm, Computers & Operations Research30(12) (2003), 1865–1886.

39.

Zhang

, Huang

, Hu

, et al., Solving 0-1 knapsack problems based on amoeboid organism algorithm, Applied Mathematics and Computation219(19) (2013), 9959–9970.

40.

Azad

M.A.K.

, Rocha

A.M.A.C.

and Fernandes

E.M.G.P.

, Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problems, Swarm and Evolutionary Computation14 (2014), 66–75.

41.

Guo

, Chang

W.L.

, Ho

, et al., Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing, BioSystems80(1) (2005), 71–82.

42.

Sanches

C.A.A.

and Soma

N.Y.

, A polynomial-time DNA computing solution for the Bin-Packing Problem, Applied Mathematics and Computation215(6) (2009), 2055–2062.

43.

Wang

, Huang

, Meng

, et al., A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation, Biosystems114(1) (2013), 1–7.

44.

Hao

, Gui-Lu

and Feng

, Quantum algorithms for some well-known NP problems, Communications in Theoretical Physics37(4) (2002), 424.

45.

Wang

, Pu

, Cao

, et al., A parallel biological optimization algorithm to solve the unbalanced assignment problem based on DNA molecular computing, International Journal of Molecular Sciences16(10) (2015), 25338–25352.

46.

Wang

Z.C.

, Huang

D.M.

, Tan

, et al., A parallel algorithm for solving the n-queens problem based on inspired computational model, BioSystems131 (2015), 22–29.

47.

Chang

W.L.

, Fast parallel DNA-based algorithms for molecular computation: Quadratic congruence and factoring integers, IEEE Transactions on Nanobioscience11(1) (2012), 62–69.

48.

Chang

W.L.

, Guo

and Ho

S.H.

, Fast parallel molecular algorithms for DNA-based computation: Factoring integers, IEEE Transactions on Nanobioscience4(2) (2005), 149–163.

49.

Jian

and Dandan

, Complex network theory and its application research on P2P networks, Applied Mathematics and Nonlinear Sciences1(1) (2016), 44–50.

50.

Rosa

and Núñez

M.L.G.

, Multiplier method and exact solutions for a density dependent reaction-diffusion equation, Applied Mathematics and Nonlinear Sciences1(2) (2016), 311–320.