# Generating DNA Origami Nanostructures through Shape Annealing
## 2 Methods
### Shape Grammars  
Simulated annealing requires neighborhood moves for each variation, which is the replacement of the current solution by the test solution. Shape annealing utilizes simulated annealing to control the search process and defines the move set through a formal language of shape known as shape grammars. Shape grammars, introduced by [PERSON], provides an effective way to concisely encode knowledge of how to legally assemble various artifact forms together through a set of shape transformation rules that are applied iteratively from a starting shape to generate a different, evolving shape [19]. These geometric shapes are typically 2D or 3D. Spatial transformations of translation, rotation, reflection, and scale, and boolean operations of union, intersection, and subtraction can be achieved using shape grammars. Generally, each shape transformation rule specifies a condition and an associated action. In addition to defining a language of form, shape grammars have been utilized for functional designs such as MEMS resonators [27] and roof trusses [28]. Thus, with shape annealing, geometric forms are generated based on the language of a shape grammar to fulfill goals and constraints through stochastic search. In the original introduction of shape annealing, a snake-like grammar was defined to pack a 2D volume (Figure 2). The insight of this paper is that the sequencing of DNA has a similar snake-like property. As such, in this work, we introduce the shape annealing methods for the design of DNA origami, providing a new generative CAD hybrid top-down and bottom-up approach that results in novel DNA sequences that fulfill a functional need without requiring a prior configuration, or envisioning of the solution. Since DNA origami is fundamentally based on the path of the scaffold that is then cirched with staple strands, the shape grammars in Figure 3 encode knowledge of how to legally assemble a continuous scaffold strand constrained to the caDNAno honeycomb lattice architecture. The grammar ensures legal designs by incorporating the dimensions of a double-stranded DNA (dsDNA) with a helical diameter of 2 nm cut into an axial length of 2.38 nm (axial rise of 0.34 nm per base). According to the mathe  
Figure 2: Snake-like shape grammars of half-hexagons: (**a**) Four simple shape grammar rules consisting of half-hexagons with a long base of one unit and a short base of one-half unit. Rule 4 is created to complete the final generated shape; (**b**) Final generated shape based on the snake-like shape grammar constrained to a 5 \(\times\) 5 unit box with the condition of no pieces overlapping. The fill pattern indicated the applied rule, where a light fill points to rule 1, a medium fill points to rule 2 and a dense fill points to rule 3 (adapted from [PERSON] [29]). lattice architecture, 7 bases is approximately 240 degrees. Therefore, a central helix can address all three nearest neighbors along its length by placing crossovers at multiples of 7 base pairs [5; 9]. The shape grammar for the generated designs generalizes the scaffold into short helical 7 base pair (bp) segments with physical dimensions of the dsDNA double helix, where potential crossovers are located at the start and end of the segment. The grammar further represents short helical segments running clockwise in the \(-\)z direction as blue, and segments running counterclockwise in the \(+\)z direction as red. The nearest neighbors of the blue and red helices are at a \(-180^{\circ}\) angle difference, where potential crossovers for the blue helix are in the order of \(0^{\circ}\), \(120^{\circ}\), and \(240^{\circ}\). The arrow labels indicate the potential crossover locations and therefore where a rule can be applied along the helix. The grammar  
Figure 3: Shape grammar example for scaffold routing when constrained to a honeycomb lattice architecture. The scaffold is sectioned into 7-base helical segments with the physical dimension of the dsDNA right-handed double helix.