Linear Strand Methods
Double Tracing
Referred to as such because of the mathematics involved, this earliest approach to self-assembly may be found in the techniques of [Adl94, ZS94, CS91], and, with modification, [SQJ04]. This method uses single strands of DNA to trace out each edge of a graph, once in each direction, binding to themselves along segments of Watson-Crick complements to form double helixes along the edges and stable branched junctions at the vertices. (See Figure 2.) For additional mathematical background on this problem see [JS02].
Figure 2: Schematic of cube from [See04] (twisting of DNA strands not shown). This uses six circular strands, but as few as two are possible.
The sequences of nucleotides are carefully specified so that only the two sides of an edge are complements of, and hence bind to, each other. Determining ds and DS: ds: The minimum number of circular single strands needed to construct the graph with a detachment-free bidirectional double covering of the edges.DS : The maximum number of circular single strands needed to construct the graph with a detachment-free bidirectional double covering of the edges.detachment-free: The path cannot separate at a vertex, for example by doubling back at an edge. Figure 3 shows examples of forbidden detachments.
Figure 3: Forbidden tracing configurations causing detachment of the construct.
strand: May then be interpreted as a facial walk of a graph embedded in an orientable surface, or equivalently as the boundary of an orientable ribbon graph- It follows from the Euler polyhedral formula that any strand number for a graph may be given by 2−V +E −2g, where V and E are the numbers of vertices and edges, respectively, of the graph, and g is the genus of an oriented surface into which the graph is embedded.- Thus, if γ is the minimum genus of a graph, and Γ is the maximum genus, then ds = 2 − V + E − 2 Γ and DS = 2 − V + E − 2γ, so the minimum strand number corresponds to the maximum genus and vice versa.
The Benefits of ds and DS:
- fewer strands - means fewer to design, and perhaps fewer incomplete or incorrect constructs - hence higher yields
- shorter strands - may be more stable, so a large number of shorter strands may be preferable for some constructions
- The relation between the strand numbers and genus means that for many important classes of graphs ds and DS are known, but in terms of the minimum and maximum genus.
Genus Questions:
- Minimum genus was shown in [Tho89] to be NP-hard in general.
- Maximum genus is more tractable, with a general algorithm in [FGM88] that finds the maximum genus of a graph with e edges, v vertices, and maximum degree d in O(evdlog⁶ v) time.
- However, the application requires not only the strand numbers, but also the intervals along each strand where it adheres to another.
Requirements of the Cycle Double Cover Conjecture (CDC):
While double covering of edges naturally suggests the CDC, the double tracing construction method has both stronger and weaker requirements.
- a cycle may not repeat an edge (in DNA constructs this is allowed)
- orientation is not considered in the CDC (a DNA strand has a natural orientation, and so the construction requires that each edge be covered once in each direction)
This construction method provides an interesting new application of graph genus. Related work can be found in [Ell04].