(665i) An Optimization-Based Approach for the Design of Self-Assembled DNA Tiles

In structural DNA nanotechnology, DNA strands exceed their
traditional role in gene expression and are being used as programmable building
blocks for nanoscale structures. This self-assembly is driven by hybridization
following the Watson-Crick rule.[1-3] Depending on the design of the DNA
strands, structures with a rich set of nanoscale features can be
self-assembled. A special class of DNA structures are the so-called DNA tiles,[4]
which are self-assembled from a relatively small number of DNA strands.
Experimental methods to self-assemble DNA tiles for a given design of DNA
strands are well developed. However, a challenge is to find the optimal design
of the individual DNA strands to self-assemble a desired DNA tile.

In general, the design of DNA strands for self-assembly of tiles
involves two steps, 1) structural design and, 2) sequence generation. For
structural design, the aim is to select optimal locations for so-called crossovers,
which involves bridging of two DNA double helices (see Figure 1). Each
crossover connects two double helices by a pair of shared single strands
DNA.[1,3] For sequence generation, an optimal sequence of nucleotides for each
DNA strand needs to be selected to enable the formation of the selected
crossovers. Generally speaking, efficient algorithms for sequence generation
exist. However, for the structural design, existing methods typically only
provide a modeling framework for prediction and visualization of a stable
structure for a given structural design (i.e., for solving the 'forward'
problem).[6-9] In contrast, finding a structural design that allows for
self-assembly of a desired final structure with high stability (i.e., solving
the 'inverse' problem) remains challenging.

The objective of this work is to investigate an optimization-based
approach for the optimal structural design of self-assembled DNA tiles. A
semi-empirical model from literature [8] is used to predict the potential
energy of a self-assembled DNA tile.

First, minimization of the potential energy for a given design
(i.e., locations of crossovers) is studied for three different types of
tiles.[5,10,11] The optimization problem was implemented in Matlab (2014a,
Mathworks, Inc.) using the solver fmincon and
in General Algebraic Modeling System (GAMS) Release 24.4.6. (GAMS Development
Corporation, Washington, DC, USA, 2015) using different non-linear programming
(NLP) solvers. Figure 2 illustrates the structural configurations of various
self-assembled DNA tiles that were found after minimization of the potential
energy. Different local minima were identified depending on the randomly chosen
initial guesses. In all cases, the structure with the lowest potential energy
corresponded to the intended structure reported in literature. Furthermore, in
all cases, a significant part of the initial guesses converged to local minima.
The structural configurations corresponding to those local minima could be
significantly different from the intended structure (Figure 1), which
illustrates the practical importance of avoiding local. Both a multi-start
optimization method and deterministic global optimization using GAMS/BARON were
investigated to identify the global minimum.

Second, self-assembly of the DNA tensegrity triangle [5,12](Figure
1) is chosen as the case to investigate model-based optimization of the
structural design. This tile has been synthesized experimentally[5] and has
practical relevance as template for protein crystallization. The optimization
problem aims to minimize the potential energy of the tile, to maximize
stability, using the orientation and position of the helices and the locations
of the crossovers as degrees of freedom. Since the length of the DNA strands is
typically short, decisions regarding the locations of crossovers are discrete
decisions (represented by integer variables). Therefore, the optimization
problem is formulated as a mixed-integer nonlinear programming (MINLP) problem.
The optimization problem was implemented in GAMS using the solver SBB, which is
based on branch-and-bound. The solution obtained with the MINLP formulation was
compared to the solution obtained by exhaustive enumeration of the integer
variables and solving an NLP problem at each node. The lowest potential energy
could be obtained by using 27 nucleotides between each crossover for an
equilateral triangle design, which matches experimental findings[5] and was
also found using branch-and-bound with a 10-fold smaller CPU time compared to
exhaustive enumeration. Finally, the design problem was also solved with the
number of nucleotides between crossovers on each side of the triangle as a
decision variable. The proposed MINLP optimization method was again able to
identify the same mixed-integer solution compared to exhaustive enumeration at
a much smaller CPU time (200-fold), which demonstrates the strength of a
branch-and-bound algorithm for structural design of self-assembled DNA tiles.

Figure 1: An example of a self-assembled DNA tile (tensegrity triangle)
and detailed view of the structure of crossovers that interlink DNA helices.

Figure 2: Identified local minima when minimizing the
potential-energy of three different types of DNA tiles with fixed locations of
crossovers. The percentage of randomly chosen initial guesses that led to each
structure is indicated below the potential energy of the structure

Reference

[1] Seeman, N. C. An overview of structural DNA nanotechnology. Mol. Biotechnol. 37,246-257
(2007).

[2] Seeman, N. C. DNA in a material world. Nature 421,427-431
(2003).

[3] Seeman, N. C. DNA nanotechnology: novel DNA constructions. Annu. Rev. Biophys. Biomol.
Struct. 27,225-248
(1998).

[4] Park, S. H. et
al. Programmable
DNA self-assemblies for nanoscale organization of ligands and proteins. Nano Lett. 5,729-733
(2005).

[5] Zheng, J. et
al. From
molecular to macroscopic via the rational design of a self-assembled 3D DNA
crystal. Nature 461,74-77
(2009).

[6] Birac, J. J., Sherman, W. B., Kopatsch, J., Constantinou, P.
E. & Seeman, N. C. Architecture with GIDEON, a program for design in
structural DNA nanotechnology. J.
Mol. Graph. Model. 25,470-480
(2006).

[7] Castro, C. E. et
al. A
primer to scaffolded DNA origami. Nat.
Methods 8,221-229
(2011).

[8] Zhu, J., Wei, B., Yuan, Y. & Mi, Y. UNIQUIMER 3D, a
software system for structural DNA nanotechnology design, analysis and
evaluation. Nucleic
Acids Res. 37,2164-2175
(2009).

[9] Pan, K. et
al. Lattice-free
prediction of three-dimensional structure of programmed DNA assemblies. Nat. Commun. 5,(2014).

[10] Wei, B. & Mi, Y. A new triple crossover triangle (TXT)
motif for DNA self-assembly. Biomacromolecules 6,2528-2532
(2005).

[11] He, Y. et
al. Self-Assembly
of Hexagonal DNA Two-Dimensional ( 2D ) Arrays. J. Am. Chem. Soc.12202-12203
(2005).

[12] Liu, D., Wang, M., Deng, Z., Walulu, R. & Mao, C.
Tensegrity: construction of rigid DNA triangles with flexible four-arm DNA
junctions. J.
Am. Chem. Soc. 126, 2324-2325 (2004).