Branched Junction Molecules

DNA nano-structures have been constructed from k-armed branched junction molecules, star-shaped molecules whose centers form the vertices of the structure. Each tile contains one vertex, and the tile arms are double strands of DNA with one strand extending beyond the other. The longer strand forms a cohesive end that can bond to any other cohesive end with complementary Watson-Crick bases, as in Figure 1, thus allowing the molecules to self-assemble.

Definitions [JMS06, Sta06]:

Tile: the combinatorial abstraction of the branched molecule

Bond edge: the abstraction of a cohesive end together with its complementary cohesive end

Cohesive end types: (letter labels) distinguish cohesive ends - a cohesive end labeled with an unhatted letter can adjoin to a cohesive end labeled with its complementary hatted label

Pot: a collection of tiles

Constructing the Graph: A target graph is constructed from these branched molecules, with a vertex of degree k realized by a k-armed branched molecule, and where two vertices in the target graph have an edge between them if and only if their two branched molecules have an arm joined between them via the complementary bases on the cohesive ends. (The joined arms form the edges of the target graph.)

The resulting DNA complex is complete if it has no unmatched cohesive ends. In general (except for various lattices), we assume the final realization of a target graph is a complete complex.

Forming a Graph From a Pot:

Notes:

Cohesive end types a and â would represent complementary sequences of bases, and so could form a bond-edge, as in Figure 1 (above).

As an example of this, let S = {a, b, . . .} be a set of labels and let Ŝ= {â, b̂ . . .} be a corresponding set of hatted labels. Combinatorially, a tile may bethought of as a vertex with half-edges labeled by elements of either S or Ŝ.

In the case of flexible armed molecule models, it is unnecessary to distinguish among permutations of cohesive end types about a vertex. However, in geometrically constrained constructions, the relative positions of the labeled half-edges is a critical consideration.

In order to guarantee the existence of a complete structure, all arms of every tile in the pot must have a complementary arm present [Sta06].

Combinatorial Problems

The notes above lead to two new graph invariants and several new combinatorial problems for graphs.

Problem: The branched junction molecules cost time, money, and effort to make (though replicating existing tiles is inexpensive).

Goal: Given a graph, we need to determine the minimum number of tile and bond-edge types required to construct a DNA complex realizing the graph. We must specify the combinatorial structure of the tiles in such a minimum set. This is equivalent to finding an edge-labeled orientation of the graph, using a minimal alphabet for the labels, with as few different labellings of the half edges about the vertices as possible, and furthermore specifying the set of different vertex types (the resulting tiles).

This problem is further confounded by the constraints of several different experimental settings.

Constraints:

- Because in the actual assembly process there are typically arbitrarily many tiles of each type present, a pot that realizes a graph G may realize many other graphs as well.

- In particular, if a pot realizes a graph G, then it could possibly realize any covering graph H of G. (A graph H covers a graph G if there is a surjective function from the vertices of H to the vertices of G that induces a surjection on the edges incident to every vertex.)

- Fortunately, in practice this has not yet been a problem (it is hard enough to get the desired construct to self-assemble, let alone anything bigger).

- However, for some experiments it may be important for the pot not to realize anything smaller than the desired graph. Thus, if say a cube is desired, the pot must realize the cube, but not permit the incidental construction of K₄’s.