Abstract
Within biology, it is of interest to construct DNA complexes of a certain shape. These complexes can be represented through graph theory, using edges to model strands of DNA joined at junctions, represented by vertices. Because guided construction is inefficient, design strategies for DNA self-assembly are desirable. In the flexible tile model, branched DNA molecules are referred to as tiles, each consisting of flexible unpaired cohesive ends with the ability to form bond-edges. We thus consider the minimum number of tile and bond-edge types necessary to construct a graph $G$ (i.e. a target structure) without allowing the formation of graphs of lesser order, or nonisomorphic graphs of equal order. We emphasize the concept of (un)swappable graphs, establishing lower bounds for unswappable graphs. We also introduce a method of establishing upper bounds via vertex covers. We apply both of these methods to prove new bounds on rook's graphs and Kneser graphs.
Introduction: The Flexible Tile Model
In the field of DNA nanotechnology, researchers leverage the predictable base-pairing of DNA (A-T, C-G) to engineer complex nanoscale structures. A prominent framework for this is the flexible tile model. In this model, the target structure is represented as a graph $G = (V, E)$. The vertices $V$ represent branched DNA molecules, known as "tiles," while the edges $E$ represent the bonds formed between complementary "sticky ends" of these tiles.
The primary goal is to design a "pot"—a collection of unique tile types and bond-edge types—that will self-assemble into the desired target graph. Since synthesizing unique DNA sequences is costly and labor-intensive, the objective is to minimize the number of unique components in the pot.
The Challenge of Scenario 3
A significant challenge in DNA self-assembly is ensuring structural fidelity. This paper focuses on the Scenario 3 constraint, the strictest design requirement. Under Scenario 3, a designed pot must only be capable of assembling into the target graph $G$. It must not accidentally form:
- Graphs of a smaller order (fewer vertices).
- Non-isomorphic graphs of the same order (different connectivity patterns).
Finding the absolute minimum number of tile types ($T_3(G)$) and bond-edge types ($B_3(G)$) required to satisfy this constraint for arbitrary $k$-regular graphs is a complex problem in discrete mathematics.
Theoretical Framework: Unswappability and Vertex Covers
To address these challenges, the authors introduce several key graph-theoretic concepts:
Unswappability
The primary mechanism for misassembly under Scenario 3 is "edge swapping." If two disjoint edges in a graph can be broken and their endpoints reconnected to form a non-isomorphic graph, the original graph is "swappable." A pot designed for a swappable graph might inadvertently produce the incorrect version. The authors focus on unswappable graphs, where every possible edge swap results in a non-isomorphic graph, providing a foundation for robust assembly.
Lower Bounds via Vertex Covers
The authors prove a fundamental relationship: for an unswappable graph, every unique bond-edge type must originate from a unique "source" vertex. Consequently, the set of these source vertices must form a vertex cover—a set of vertices such that every edge in the graph is incident to at least one vertex in the set. This establishes a hard lower bound: for unswappable graphs, $B_3(G) \ge |K|$, where $|K|$ is the size of the minimum vertex cover.
Upper Bounds and Neighborhood Independence
To establish upper bounds, the authors provide a construction method. By identifying a vertex cover that satisfies "neighborhood independence"—a condition ensuring that each vertex's connections are mathematically unique—they can orient edges to create a foolproof DNA pot.
Key Results on Symmetric Graphs
The authors applied these methods to two specific families of highly symmetric $k$-regular graphs:
- Rook's Graphs ($R_{m,n}$): Representing rook moves on an $m \times n$ chessboard, these graphs were found to have an optimal pot size for $m,n \ge 4$ consisting of exactly $mn$ tile types and $mn - n$ bond-edge types.
- Kneser Graphs ($Kn(n,k)$): For these combinatorial graphs, the authors proved that every vertex requires a unique tile type. For the subset where $k=2$ and $n \ge 6$, they established an exact bond-edge bound of $\binom{n-1}{2}$.
Conclusion and Future Directions
This work successfully translates biochemical constraints into solvable graph theory problems. However, limitations remain. Checking for unswappability involves the Graph Isomorphism problem, and finding minimum vertex covers is NP-hard. Future research will focus on developing more efficient algorithms for these checks and extending these theorems to non-regular graphs with varying degrees of connectivity.
Summary updated