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).