v) is selected sequentially such that clauses C1, C2, C3, …., Cm are satisfied one after another. Thus, the first extraction operation is selected to make C1 satisfiable. All DNA solutions satisfying C1 are then subjected to the next extraction operation, which makes C2 satisfiable and so on. If any solution is left in the tube after sequentially satisfying C1, C2, C3, …., Cm clauses, then it implies that the given Boolean formula is satisfiable for the sequence remained in the tube. If no solution is left, then it implies that the given Boolean formula is not satisfiable.
Consider a simple example of (x1∨x2) ∧ (¬x2∨x3) for illustration. In this formula, variables x1, x2, and x3 are present. The objective is to find a binary string for x1 x2 x3, which satisfies the clauses C1 = (x1∨x2) and C2 = (¬x2∨x3). Boolean formula (x1∨x2) ∧ (¬x2∨x3) will be solved by making the test tubes for all possibilities, as given in Table 2.1. There are three variables, x1, x2, and x3, represented by “0” or “1,” which leads to total eight possibilities (23 = 8). These eight possible ways are encoded in the form of DNA molecules just by pouring all individual sequences of vertices and edges into the test tube t0 and performing the ligation. Next, the extraction operation is performed on this tube t0. The first extraction operator is E (t0, 1, 1), which extract values having the first bit as “1” since this makes first clause C1 = (x1∨x2) true. Also, the second bit corresponding to x2 can make C1 = (x1∨x2) true. Therefore, all remaining solutions that do not satisfy the E (t0, 1, 1) are extracted in the tube t1′. These solutions from t1′ are then subjected to the second condition where x2 becomes 1. Thus, the next extraction operation, t2, is
Table 2.1 The sequence of extraction operations for a given illustrative SAT problem [(x1∨x2) ∧ (¬x2∨x3)].
| Test tube | Operator | Values present |
|---|---|---|
| t 0 | 000, 001, 010, 011, 100, 101, 110, 111 | |
| t 1 | E(t0, 1, 1) | 100, 101, 110, 111 |
|
|
t0 − t1 | 000, 001, 010, 011 |
| t 2 |
|
010, 011 |
| t 3 | t1 + t2 | 010, 011, 100, 101, 110, 111 |
| t 4 | E(t3, 2, 0) | 100, 101 |
|
|
t3 − t4 | 010, 011, 110, 111 |
| t 5 |
|
011, 111 |
| t 6 | t4 + t5 | 100, 011, 101, 111 |
2.2.3 Smith's Model
The surface‐based DNA computing model was introduced by Smith et al. [4]. In this model, DNA molecules are attached to a solid surface, instead of DNA molecules floating in a solution. Solid‐phase nucleotide synthesis is used for the immobilization of the nucleotides on the solid surface. The procedure given by Smith et al. [4] involves following six steps: (i) make, (ii) attach, (iii) mark, (iv) destroy, (v) unmark, and (vi) read out as shown in Figure 2.3.
Figure 2.3 Representation of surface‐based DNA computing method [4].
In this procedure, first, the sequence corresponding all possible combinations of variables is designed in step (i). To represent each combination of variables in a SAT problem, Smith et al. [4] used the DNA sequences consisting of unique DNA sequences at each end and variable DNA sequences in the middle for hybridization such as T15GCTTvvvvvvTTCG. In this, the variable DNA sequences are represented by “vvvvvv.” The one end of these sequences has a spacer [15 “T” nucleotides (T15)] that attaches to the surface. In step (ii), the sequences generated for all combinations are attached to the solid surface, as shown in Figure 2.4.
