Optimal Constructions for DNA Self-Assembly of $k$-Regular Graphs

Lisa Baek, Edward L. Bove, Michael Cho, Xingyi Zhang, Leyda Almodóvar, Amanda Harsy, Cory Johnson, Jessica SorrellsarXiv 2025 · DOI · arXiv

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 flexible tile model: DNA strands with complementary sticky ends assemble into connected structures.

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:

  1. Graphs of a smaller order (fewer vertices).
  2. 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.

Mapping tile types to a target graph: A set of unique tile types (left) is designed to assemble into a specific $k$-regular graph (right).

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

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.
BibTeX
@misc{baek2025optimal,
  author = {Lisa Baek and Edward L. Bove and Michael Cho and Xingyi Zhang and Leyda Almodóvar and Amanda Harsy and Cory Johnson and Jessica Sorrells},
  title = {{Optimal Constructions for DNA Self-Assembly of $k$-Regular Graphs}},
  year = {2025},
  eprint = {2502.03716},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.03716},
  howpublished = {arXiv},
}
Figure