Ans
Directed Hamiltonian Cycle:

The first step toward solving the DHC problem lies in finding a way to represent the components of a directed graph G = (V,E) (i.e. vertices and edges). Next the operations needed to determine the existence of a valid Hamiltonian cycle are presented.

Oligo Selection:

We’ll choose unique, 20-base oligos to represent each vertex vi V. Wel’ll notate the n vertex oligos as x1y1… xnyn where xi represents the 10 bases oriented at the 5’ end and yi is the following 10 bases ending at the 3’ end. The edge oligos will be choses based on the vertices that define them using the following scheme. For each edge (vi, vj ) E, we’ll use yixj to represent it, with one exception. For each edge that includes the starting vertex vs, we’ll use the entire complement of xsys as follows. For an edge leaving vs, (vs, vj), we’ll use xsysxj and for an edge entering vs (vi,vs), we’ll use yixsys. When these oligos are placed in solution, complementary oligos will anneal to one another, resulting in valid paths on G. How does this work? Observe that each edge oligo, yi xj , will anneal to its respective vertex oligos, xi yi and xj yj, to form xi yixj yj. Furthermore, if there is an edge yixk and vertex xk yk, a path of length two is created resulting in xi yixj yjIk yk. It would be prudent now to explain why the modified representation of edges containing vs was chosen. Recall that we’re specifically looking for paths that begin and end with vs. So when a path contains an edge leaving vs say (vs, vj ), it will form a strand of the form xsys xj yj. The only possible oligo that can anneal to the beginning of this strand is xsys, forcing strands containing this edge to represent paths beginning with vs. The same logic was used for our representation of edges entering vs, resulting in paths that must terminate at vs.

Solution of DHC:

When the oligos chosen in the previous are placed in solution, they will anneal in parallel to form strands representing possible paths on G. It remains for us to determine if one of these paths represents a hamilonian cycle on G. 1. Find all paths that begin and end with Vs. 2. Find all paths containing exactly n + 1 vertices. 3. Find all paths that enter each vertex once. 4. Determine if any strands are left. If so, then there is a Hamiltonian cycle on G. The first step, as stated above, is finding all paths that begin and end with Vs. This is accomplished using the amplification operation with oligos xsys and xsys,resulting in the amplification of only those double strands that begin and end with Vs. Next, the length operation is used to find those double strands that encode a path of length n + 1 vertices, or 20(n+1) bases. Now we are left with finding those paths that enter each vertex once. This is accomplished by performing a series of n extract operations. First, the double strands are melted into single strands. Then, for each vertex, vi, the extract operation is run using xi yi , resulting in the extraction of all strands containing vi. After the completion of all extractions, only those strands containing all n vertices will remain. Finally, the detect operation can be used to determine if any strands remain. If so, then those strands represent solutions to the problem. If not, then there is no Hamiltonian cycle in the graph G.

Analysis:

Each step of the procedure, except for step 3, represents a single biological operation. If we consider each biological operation to take 0(1) time, then steps 1,2,4 together are 0(1). Step 3 requires n extract operations. Therefore, the entire procedure completes in 0(n) biological operations which is linear in the total number of vertices. So the DNA computing model produces an efficient solution to the directed Hamiltonian cycle problem.