for each vertex and edge are mixed together to form double‐stranded DNA (dsDNA) representing all possible paths in the given supergraph in the ligation step. Since each vertex must be visited exactly once in the Hamiltonian path, a graph of N (= 5) vertices having each vertex encoded with L (= 20 bp) nucleotides must comprise total N × L (= 100 bp) nucleotides. Therefore, all dsDNA molecules of different lengths obtained after the ligation step are separated using gel electrophoresis. In this step, the gel slice corresponding to the band of the desired length (= 100 bp) is then separated from the gel by a cutter as the correct DNA sequence corresponding to an optimal solution is expected to be present only in this slice. Further, this band may comprise some undesired solutions with the correct length of 100 bp. The DNA solutions are extracted from the gel slice and are amplified using PCR to generate enough number of desired sequences of DNA representing the solution to the given HPP beginning with one and ending with five. Subsequently, the DNA solution undergoes affinity separation process using streptavidin–biotin magnetic beads to check the presence of vertices 1–5 sequentially one after another in tubes 1–5. The PCR products of these tubes are then analyzed by gel electrophoresis where the bands of respective lengths are obtained, signifying the location of these vertices in the entire sequence. If these tubes give the bands of 20, 40, 60, 80, and 100 bp, then it confirms that all N (= 5) vertex are visited, and depending on the location of the primer, the location of the vertex in the entire sequence is also determined. For a given example, the Hamiltonian path is 1–3–4–2–5, which corresponds to the bands of 20, 40, 60, 80, and 100 bp, respectively, on the gel image.
2.2.2 Lipton's Model
Lipton [3] solved the SAT problem with a linear complexity of biomolecular operations. In SAT problem the operators logical OR (∨), logical AND (∧), and logical NOT (¬) along with the variables (x1, x2, x3, …, xn) constitute a Boolean formula, e.g. (x1∨x2) ∧ (¬x2∨x3). In this formula, a literal can be either a variable or the negation of the variable, e.g. x1 or ¬ x1. The clause (Ci) is a disjunction of literals, e.g. (x1∨x2). Finally, a Boolean formula is a conjunction of clauses [e.g. (x1∨x2) ∧ (¬x2∨x3)] such as C1 ∧ C2 ∧ C3 ∧ …. Cm for m clauses. In a SAT problem, the objective is to confirm whether there exists a set of input conditions (i.e. the input variables, x1, x2, x3, …, xn ∈ [0, 1]) for which a given Boolean formula is satisfiable, i.e. the output is 1.
To solve the SAT problem, first, the variables are arranged in a string as x1 x2 x3 … xn. In Lipton's model, this variable string, x1 x2 x3 … xn, is represented in a graph form. Since the variables can have 0 or 1 values, the vertices with no bars (e.g. x1, x2, etc.) represent the 1 value, whereas those with bars (e.g.
Figure 2.2 Lipton's graph [3] for constructing a binary number for a general variable string (x1 x2 x3 … xn).
The objective is to extract a binary sequence for x1 x2 x3 … xn from all possible combinations that satisfy all the clauses C1, C2, C3, …, Cm. To solve this problem, the ssDNA sequences of x1,
