# Modeling DNA Nanodevices Using Graph Rewrite Systems

### Venue

Springer International Publishing (2017), pp. 347-395

### Publication Year

2017

### Authors

Reem Mokhtar, Sudhanshu Garg, Harish Chandran, Hieu Bui, Tianqi Song, John Reif

### BibTeX

## Abstract

DNA based nanostructures and devices are becoming ubiquitous in nanotechnology with
rapid advancements in theory and experiments in DNA self-assembly which have led to
a myriad of DNA nanodevices. However, the modeling methods used by researchers in
the field for design and analysis of DNA nanostructures and nanodevices have not
progressed at the same rate. Specifically, there does not exist a formal system
that can capture the spectrum of the most frequently intended chemical reactions on
DNA nanostructures and nanodevices which have branched and pseudo-knotted
structures. In this paper we introduce a graph rewriting system for modeling DNA
nanodevices. We define pseudo-DNA nanostructures (PDNs), which describe the
sequence information and secondary structure of DNA nanostructures, but exclude
modeling of tertiary structures. We define a class of labeled graphs called DNA
graphs, that provide a graph theoretic representation of PDNs. We introduce a set
of graph rewrite rules that operate on DNA graphs. Our DNA graphs and graph rewrite
rules provide a powerful and expressive way to model DNA nanostructures and their
reactions. These rewrite rules model most conventional reactions on DNA
nanostructures, which include hybridization, dehybridization, base-stacking, and a
large family of enzymatic reactions. A subset of these rewrite rules would likely
be used for a basic graph rewrite system modeling most DNA devices, which use just
DNA hybridization reactions, whereas other of our rewrite rules could be
incorporated as needed for DNA devices for example enzymic reactions. To ensure
consistency of our systems, we define a subset of DNA graphs which we call
well-formed DNA graphs, whose strands have consistent 5' to 3' polarity. We show
that if we start with an input set of well-formed DNA graphs, our rewrite rules
produce only well-formed DNA graphs.