| 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.
Figure 2.4 Representation of surface‐bound DNA sequence.
In step (iii), the sequences corresponding to the satisfaction of each clause are marked by hybridizing these with the complementary sequences corresponding to “vvvvvv.” In step (iv), all single‐stranded sequences remaining after the hybridization are destroyed by treating with Escherichia coli Exonuclease I. In step (v), all hybridized sequences are unmarked to get the single‐stranded molecules for all the remaining surface‐bound sequences. Steps (iii)–(v) are repeated for all the clauses one after another. The unmarked sequences remaining at the end are analyzed in a readout operation using PCR in step (vi).
The procedure is explained in the context of the same illustrative SAT problem (x1∨x2) ∧ (¬x2∨x3) of three variables (x1, x2, x3) described earlier. This problem has a solution space of size 8 (each variable can be either “1,” or “0,” total solution space = 23). All combinations for this problem are shown in the second row ( corresponding to the test tube t0) of Table 2.1. The problem involves two clauses: C1 = (x1∨x2) and C2 = (¬x2∨x3). The SAT is checked for these clauses one by one. C1 = (x1∨x2) is not satisfied only if x1x2x3 is represented by {000} and {001}. Therefore, the complementary sequences for all “vvvvvv” except for the above two clauses are hybridized. This eliminates the above two combinations. The remaining hybridized combinations are unmarked. Next, the SAT of C2 = (¬x2∨x3) is checked. C2 = (¬x2∨x3) is not satisfiable for {010} and {110}. Except these, all the sequences are allowed to hybridize. This leads to hybridization of {011}, {100}, {101}, and {111}. These are unmarked and identified in a readout step using PCR.
2.2.4 Sakamoto's Model
Sakamoto et al. [5] introduced a hairpin formation model for solving an SAT problem using molecular biology techniques. For a given illustrative SAT problem (x1 ∨x2) ∧ (¬x2 ∨x3), literal strings (x1, ¬x2), (x1, x3), (x2, ¬x2), and (x2, x3) are formed. A literal string is a string used to encode the given formula with conjunctions of the literals selected from each clause. The literal strings are obtained by concatenating of DNA sequences corresponding to each literal in a ligation step. In these literal strings, if a variable is represented in both original and negation form, then it violates the SAT condition of the given SAT problem. The literal strings without such violation in which a variable is represented only and at least in one form (either actual or negation) constitute a satisfiable solution to the given SAT problem. In Sakamoto's model, possible literal strings are first obtained by ligation. A length of the literal string equals to the number of clauses × nucleotides used for each literal. Subsequently, the obtained literal strings are subjected to temperature variation, which leads to a hairpin formation if a variable is represented in its original and negation form. The restriction enzyme destroys all such hairpins. These solutions are readily eliminated in the subsequent gel electrophoresis operation where only the literal strings with the desired