# Generating DNA Origami Nanostructures through Shape Annealing
## 1 Introduction  
Structural DNA nanotechnology enables the creation of complex polyhedral nanostructures due to the predictability of Watson-Crick base-pairing, wherein adenine (A) and guanine (G) form hydrogen bonds with thymine (T) and cytosine (C) [1, 2, 3]. Due to the programmable binding of nucleobases, the field of DNA nanotechnology offers an unmatched ability to control the formation of arbitrarily shaped and biocompatible DNA nanostructures [4]. The DNA origami technique is a self-assembly method wherein hundreds of short \"staple\" oligonucleotides direct the folding of a long single-stranded DNA (ssDNA) \"scaffold\" to form multilayer and wireframe DNA assemblies (Figure 1) [2, 5]. Recently, DNA origami has served to create functional applications such as multifluorophore beacon sensing platforms [6], cargo-sorting robots [7], and drug delivery vehicles [8]. With increasing functional applications, the research community has pioneered innovative tools to facilitate the design process. CaDNAno is a popular computer-aided design (CAD) tool that revolutionized the design process, providing a graphical-user-interface (GUI) and computationally inexpensive method to manually create DNA origami designs from the bottom-up [9]. CaDNAno designs can be built using a square or honeycomb lattice architecture, providing guidance on the available and optimal crossover locations as well as an auto-stapling function. While caDNAno has been so pivotal to the growth of thefield, it heavily relies on the expertise of the designer, who must first conceptualize each design before manually implementing the concept. The challenges of manual design can incentivize designers to limit their structures to the simplest geometries. More critically, the manual nature of the process makes it difficult to implement and therefore to compare a range of possible designs to address a given application. Automated tools have the potential to accelerate the design process and broaden the design space. One powerful approach demonstrated by the tools vHelix [11], DAEDALUS [12], PERDIX [13], and TALOS [14] is the automated generation of nanostructure designs from 3D polyhedral meshes. These tools compute the scaffold routing and staple sequences to create wireframe DNA origami designs from input meshes. MagicDNA is a semi-automated design tool that computes scaffold routing and staple generation from a line model with detailed dimensions of the final design as input [15]. MagicDNA enables an iterative computer-aided engineering (CAE) approach to the design of DNA origami. Thus, current automated tools have enabled automation of key portions of the design process, but they are limited to an approach (top-down) that requires a designer to fully conceptualize the structure. However, it is important to note that the source of the design comes entirely from the user. Currently, DNA origami design optimization is performed iteratively by human designers, where even veteran designers often get stuck in an infinite iterative design loop in search of the ideal design [16]. Here, we present a novel, formal approach for optimizing the design process for DNA origami through automation. This approach addresses current limitations by computing optimal scaffold routing with only a set of constraints and desired configurations. This is achieved through shape annealing [17], which is an integration of the simulated annealing algorithm, a stochastic optimization technique [18], and shape grammars, which are a formal rule-based generative design method that concisely defines relationships between geometric shapes [19]. Shape annealing generates optimally directed shapes by controlling the selection and implementation of shape transformation rules to evolve a starting shape as the algorithm progresses. In our first demonstration of this approach, we start with a 3D polyhedral mesh of arbitrary size as input and our algorithm explores the design space to create a variety of unforeseen and legal designs.