Optimal Constructions for DNA Self-Assembly of $k$-Regular Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913681186488320 |
|---|---|
| author | Baek, Lisa Bove, Ethan Cho, Michael Zhang, Xingyi Almodóvar, Leyda Harsy, Amanda Johnson, Cory Sorrells, Jessica |
| author_facet | Baek, Lisa Bove, Ethan Cho, Michael Zhang, Xingyi Almodóvar, Leyda Harsy, Amanda Johnson, Cory Sorrells, Jessica |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Constructions for DNA Self-Assembly of $k$-Regular Graphs Baek, Lisa Bove, Ethan Cho, Michael Zhang, Xingyi Almodóvar, Leyda Harsy, Amanda Johnson, Cory Sorrells, Jessica Combinatorics 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. |
| title | Optimal Constructions for DNA Self-Assembly of $k$-Regular Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.03716 |