Graphs made of one single stranded DNA molecule.

Besides many developed techniques in working with DNA the researchers are still more confident that a complex graph structure made of DNA would be much simpler to detect if it is made of one single stranded DNA molecule [4,5,28]. If a circular double stranded molecule is heated and denatured, the result is two linked loops made of single stranded DNA. This may cause difficulties in separating the desired molecules. In the previous section we described two algorithms for solving computational problems by DNA molecules where in both cases during the process of computation a graph structure was constructed. In the algorithm for HCP, the final solution did not depend on whether the graph structure could be distinguished or not, but in the case of 3VC, the final result depends on how well we can determine the formation of a DNA graph structure that corresponds to our original graph. As a mathematical problem we are faced with a question: can we characterize the graphs that can be constructed by one single stranded DNA molecule?

We can state the problem mathematically. Let G be an undirected graph with set of vertices V and set of edges E. Let $\bar G$ be a directed graph obtained from G by replacing each edge $e\in E$ with a pair of directed edges e⁺, e^- with opposite orientation. If e is incident to vertices v_e,w_e then we write e⁺=(v_e,w_e) and e^-=(w_e,v_e).

A path $p=e_1\cdots e_n$ in $\bar G$ is a strand path if p is a loop (starts and ends at the same vertex) such that $e_i\ne e_j$ if $i\ne j$ ( $i,j=1,\dots,n$). In particular, e⁺e^- is a strand path for each edge $e\in E$.

The graph G is s-DNA covered if there are s strand paths $p_1,\dots,p_s$ in $\bar G$ such that for every edge e of $\bar G$ there is a unique i such that p_i passes through e.

Using the construction from the previous section we can easily show that every graph can be s-DNA covered for some s. In the DNA graph structure every DNA strand corresponds to a strand path p. We denote with c(G) the minimum of all s such that G is s-DNA covered.

Problem 1: given a graph G, determine c(G).

Problem 2: characterize graphs G such that c(G)=1.

We refer to the graph in Fig. 2. Two different DNA structures of the same graph are presented in Fig. 4 and in Fig. 8. In the first case, G is 3-DNA covered and in the second case it is 1-DNA covered. So c(G)=1.

  

Figure 10: Different connections in a vertex of degree 3.

Every vertex in a graph (with degree greater than 2) can be described by 3-junction molecules (by extending the body of the central part of the vertex molecule) [28]. In Fig. 10 two 3-junction molecules presenting one vertex are depicted. The difference between these two molecules is in the connection between the edges (arms) that is established. The molecule (b) is essentially same as the molecule (a). If we twist the sides B and C in (b) so that C comes at the top and B comes on the right, we have the same structure molecule as in (a). [We note that ``twist''is used only intuitively for the purpose of the theoretical argument. Twist might not be a good way to show differences in configuration for DNA [28]. If we set a reference point at A, a half-turn difference in the length of the double helix at side A reverses the positions of B and C in space.]

When the 3-arm branched molecule becomes part of a 3D DNA structure, the three single strands can be part of three, two or one circular single stranded molecule. If they are part of three circular single stranded molecules then, as shown in Fig.11 (i.a), by changing the connection from (a) to (b) in Fig.10, the three circular single stranded DNA molecules become one. After the change in the connection, one circular single stranded DNA molecule either becomes three (as in Fig.11 (i.a)) or remains to be one. (Fig.11 (i.b)). If we have two circular single stranded DNA molecules, by changing in between connections ((a), (b) in Fig.10) the number of strands remains at 2 (Fig.11 (ii)).

We say that a graph is weakly connected if there is an edge e such that if we remove e from G then G becomes disconnected. Using the change of connections within 3-armed branched molecules as shown in Fig.11 we can show the following:

  

Figure 11: Cases of moving between connection (a) and (b) in Figure  10.

Proposition. If G is a planar graph that is not weakly connected, then $c(G)\le 2$.

There are examples of planar weakly connected graphs with c(G)>2. We are not sure whether the above proposition holds for graphs with arbitrary genus.