The Hamiltonian Cycle Problem.

Let G be a finite graph with V(G) the set of vertices and E(G) the set of edges. A Hamiltonian cycle c of G is a cycle that goes through every vertex exactly once. The Hamiltonian cycle problem (HCP) asks whether a given graph G has a Hamiltonian cycle.

  

Figure 2: An example of a graph.

We will consider the graph presented in Fig.2 as an example. The cycle v₁v₆v₄v₃v₂v₅v₁ is a Hamiltonian cycle. Of course, there are many other cycles that are not Hamiltonian, for example, v₁v₆v₅v₁ or the loop v₂v₅v₁v₂v₅v₁v₂.

We construct the graph by using k-armed branched molecules for each k-degree vertex. For the example presented in Fig.2, we will need one 2-armed branched molecule (which is just a regular double-stranded DNA molecule), four 3-armed branched molecules and one 4-armed branched molecule. The 3'end extension of each arm (representing one end of an edge) is complementary to the 3'end of the arm (representing the other end) of the same edge. Since a cycle passing through a vertex uses only two edges incident to the vertex, there are $\left( \begin{array}{c} k \\ 2 \end{array} \right)$ possible ways for a cycle to pass through a vertex. Every path may appear in two opposing DNA orientations within the molecule, hence, for each k-degree vertex we form $2\left( \begin{array}{c} k \\ 2 \end{array} \right)$ k-armed branched molecules that represent that vertex. Each one of these molecules will represent one way a cycle could pass through the vertex. To ensure that only that path will be used, we phosphorylate the 5'end of that connection. The ligase enzyme bonds, ``ligates'' the beginning of one DNA strand to the end of another DNA strand, but would not ligate (connect) ends if the 5'end is not phosphorylated at the appropriate place. We illustrate this in Fig.3 where we show six molecules representing six different paths through a vertex of degree 4. The stars indicate the 5'end that will be phosphorylated. There will be six other molecules that establish that same connections between the edges but with the other orientations.

  

Figure 3: Six molecules representing a vertex with degree 4. The four codes A,B,C,D within the single stranded 3'ends encode the four edges incident to the vertex.

The molecules are designed such that each single strand of the k-armed branched molecule has a constant length (say n). All vertex building blocks are combined and their compatible ends are allowed to form double-stranded DNA. The resulting molecules that have no open ends represent graphs; copies of the original graph, or covering graphs of the original graphs.

Proposition. Let $C=\{G_1,\dots,G_m\}$ be the set of graph structures G_i that are obtained by adding all building block molecules in a test tube and allowing them to join. Assume that C contains all possible graph structures. Let c be a cycle in the graph G. Then there is $G_j\in C$ that contains a circular single-stranded DNA molecule that encodes c.

The proof of this proposition follows from the design of the vertex building blocks.

The algorithm for the HCP has the following four steps:

• Combine all vertex building blocks in a single test tube and allow the compatible ends to hybridize and to form double-stranded DNA. The ``nicks'' that have 5'end phosphorylated are ligeted by a ligase. At this point, graph structures that represent covering graphs of the original graph need to be removed. Covering graphs are much more complex and heavier by molecular weight, hence their removal can be done by gel electrophoresis. (The problem with the covering graphs is addressed in the next section.) Gel electrophoresis is a technique that discriminates molecules of different sizes and different geometry and topology of DNA ([3,7,36,37]).

• Heat the molecules to 95⁰C degrees. Molecules are denatured and the only circular molecules that are left are cycles of the graph. We remove non-circular DNA strands from the test tube. There are several ways that this can be performed for example by an exonuclease enzyme that recognizes the open ends or by gel electrophoresis. The exonuclease virtually destroys to single nucleotides molecules that are not circular.

• We choose a vertex v and use as PCR primers oligos that are complementary to the strands forming the building blocks of that vertex. The PCR amplifies the molecules and generates double stranded molecules that encode cycles that pass through v. Polymerase chain reaction (PCR) is a standard technique in molecular biology that cycles about 30 times through two or three temperature changes, uses DNA polymerase enzyme and produces an exponential increase of a given target molecule. We refer the reader to Ausubel et al. [3] for details.

• By gel electrophoresis we select molecules that are mn in length, where m is the number of vertices in the graph and n is the length of the single strands used for the vertex building blocks. If any molecules are recovered, then the answer to the HCP is ``yes'' otherwise is ``no''. We note that in parallel with the main experiment another experiment used as a positive control is carried out. This experiment is performed for a graph for which we know a Hamiltonian cycle exists. Its success will confirm that our main experiment, producing an answer ``no'', is successful. This technique for carrying out positive and (or) negative control experiment is a standard technique in molecular biology and is an experimental necessity since many laboratory protocols are not 100% efficient.

  

Figure 4: A graph structure that contains a Hamiltonian cycle.

One DNA graph structure for the graph in Fig. 2 that would be obtained after the first step of the algorithm is presented in Fig. 4. The colored lines indicate the three DNA single stranded molecules that make up the graph structure. The blue strand indicated with a dotted line is a circular single-stranded molecule that encodes the Hamiltonian Cycle. The stars indicate nicks that are ligated.