# Generating DNA Origami Nanostructures through Shape Annealing
## 2 Methods
### Shape Annealing  
Shape annealing utilizes the simulated annealing algorithm to control the application of randomly selected shape rules at a given state. The pseudocode in Algorithm 1 provides a more detailed description of how the shape annealing algorithm works. Figure 4 illustrates examples of the shape annealing algorithm for scaffold routing when constrained to a honeycomb lattice architecture. A feasible shape rule is selected from the language and applied to the current design state. If the new design complies with the defined constraints, it is sent to the Metropolis algorithm, where the new state is compared to the old state. If the new state complies with the desired design features, it is accepted; if not, the old state is retained. In this current work, the grammar has a reversal rule (Figure 3c) applied to rules 1 and 2 (Figure 3a,b) to prevent rapid convergence on an inferior solution by enabling the algorithm to back out of local solutions. The rules in Figure 3 define the design space used to create DNA origami designs consisting of a continuous scaffold strand.  
Figure 4: Shape annealing algorithm for scaffold routing when constrained to a honeycomb lattice architecture. Key steps are initializing the temperature, verifying desired goal with metropolis function, checking whether the limit and equilibrium has been reached, and reducing the temperature. Key parameters are the temperature (T), mutations (n), limit, and reduction factor (\(\alpha\)): (**a**) General flowchart of the shape annealing algorithm.; (**b**) Two examples of rule applications based on objective minimization. The top example shows the shape rule 3 (reversal rule) accepted with a decrease in objective function. The bottom example shows the shape rule 1 (additive rule) accepted with a probability due to an increase in objective function.  
In the shape annealing algorithm, the number of outer loop iterations, which is determined by the reduction factor (\(\alpha\)), the number of inner loop iterations, which is the mutations (n), the initial temperature before the algorithm proceeds (T), and the limit, which is the number of accepted shapes within the inner loop, must be determined to ensure convergence on good solutions. By adjusting these key parameters, the shape annealing algorithm will generate unique shapes. Figure 4a displays a generic flowchart of the shape annealing algorithm, while Figure 4b displays examples of rule applications with objective function calculations.  
```
1: initialize T, limit, n, \(\alpha\)
2: generate initial_shape
3: state = evaluate(initial_shape)
4:procedureShape Anneal(state, T, limit, n, a) \(t\rightarrow\) key parameters
5:while T > 0 do
6: success=0, i =0
7:for\(i\) to ndo\(t\rightarrow\) mutations=\(n\)
8: prev_state=state
9: new_shape=random_rule()
10:if new_shape complies with constraints then
11: new_state=evaluate(new_shape)
12: test = metropolis(new_state, prev_state, T)
13:if test then
14: state=new_state
15: success += 1
16:endif
17:endif
18:if success>limitthen
19: break
20:endif
21:endfor
22:if success=0 then\(t\rightarrow\) equilibrium
23: break
24:endif
25:\(T=T^{*}\alpha\)
26:endwhile
27:endprocedure
```  
**Algorithm 1** Shape annealing algorithm