The proposed research creates new mathematical theory in the areas of graph polynomials and topological graph theory motivated by structural problems arising from self-assembling DNA nanostructures. Because the targeted nanostructures are often graphs (e.g. polyhedra), this application is a rich and natural source of appealing graph theoretical problems. Specifically, we will provide optimal design strategies in the form of algorithms and constructive proofs for new graph invariants corresponding to the minimum number of molecular components necessary to build a target graph under various laboratory settings. Furthermore we will determine the combinatorial structures of these building blocks, and how they may be assembled into the desired nanostructure. One method of producing self-assembling DNA nanostructures involves designing linear single strands of DNA that form double helixes along the edges of the desired graphical structure. Currently, these may be specially designed double strands, or a single long scaffolding strand held in place by many short staple strands, but either way, optimal paths for the strands through the target graph must be determined. A second construction method for self-assembly of DNA nanostructures uses k-armed branched junction molecules, called tiles, whose arms are double strands of DNA with one strand extending beyond the other. These arms attach to one another when the extended segments consist of complementary bases, thus forming the edges of a graphical structure. Combinatorially, tiles may be represented by vertices with labeled half-edges. Here the minimum number of tiles required and their combinatorial structures must be determined.
Two new graph invariants together with generalized transition polynomials, the topological Tutte polynomial, cycle double coverings, and genus results from topological graph theory apply to minimizing the molecular building blocks used in self-assembling nanostructures. For linear single strand methods, we will develop optimal strategies for locating the strands, characterize graphs that may be good candidates for these construction methods, and use graph polynomials to capture the topological properties of these constructs. For branched junction molecule methods we will provide explicit combinatorial descriptions of tile sets achieving the minimum number of tile and bond-edge types, and efficient algorithms for generating these sets. This is done under a range of different laboratory settings: whether flexible or rigid armed tiles are used, whether or not the incidental creation of same-size or smaller graphical complexes is acceptable, and whether the target graph is of fixed size (e.g. a polyhedron) or arbitrarily large (e.g. a lattice).
We have created new mathematical theory in the areas of graph polynomials and topological graph theory motivated by structural problems arising from self-assembling DNA nanostructures. Because the targeted nanostructures are often graphs (e.g. polyhedra), this application is a rich and natural source of appealing graph theoretical problems. Specifically, we have provided optimal design strategies in the form of algorithms and constructive proofs for new graph invariants corresponding to the minimum number of molecular components necessary to build a target graph under various laboratory settings. Furthermore we have determined the combinatorial structures of these building blocks, and how they may be assembled into the desired nanostructures. This has been a highly productive project, with outcomes including a SpringerBriefs monograph, a book chapter, 11 papers, two software programs, a contract for a CRC Handbook on the Tutte Polynomial and Related Topics, over 40 invited PI talks, over 40 undergraduate presentations, and a project website. We have also provided design strategies for specific projects to both Seeman’s lab at NYU and Goddard’s lab at CalTech. We have developed mathematical problem formulations and graph theoretical models for both branched junction molecule and origami threading methods based on design constraints supplied by ongoing collaboration with Seeman. We have provably optimal design strategies for common classes of graphs on flexible armed branched junction molecules. We have significantly advanced and unified an important branch of graph polynomials, those involving precisely the ribbon graphs that best model self-assembled graphical DNA nanostructures. In doing so, we described twisted duality for ribbon graphs, which model double-stranded DNA structures, and suggest a strategy for reassembling constructions. We have numerous new results for various ribbon graph polynomials, including restatements of the 4-colour theorem. We have extended the Tutte polynomial to much broader statistical mechanics applications, and made a surprising connection between list coloring and the Potts model. We have written computer code to generate all possible geometric configures of tiles (branched junction molecules) with up to 12 arms, and found classes of structures which may be self-assembled efficiently. We have written software that applies crystallographic symmetry groups to tile-like structures. We proved that in general optimal routing of the scaffolding strand for origami constructions is computationally intractable, even in some very restricted cases. However, we have implemented a fast algorithm for solving the related edge-specified Eulerian Superpath problem for finding origami threading for nanostructures. We have determined knotted crystal structures realizing any knot or link topology within the fundamental cell of a crystal. We have also continued our collaboration with Ned Seeman, for example providing a very challenging, provably optimal, origami folding design strategy for his lab to build a cubeoctahedral component of a DNA lattice. We have also provided a hybrid origami/tiling design strategy that may be used to assemble a patch structure of controlled size that can adhere to a cell surface. In addition, a Research Experience for Undergraduates formed an integral component of this project. We worked extensively with students, particularly first-generation, female, and rural students. Four or more Saint Michael’s College students each academic year and summer participated in both the theoretical (mathematical) and pragmatic (implementation) aspects of developing graph theoretical models for various problems arising from applications in self-assembling nanostructures. Through this REU, we were able to: 1) Advance the overall project goals through student contributions, 2) provide formative experiences for students that advance their careers as future mathematicians and scientists, and 3) build student proficiency in the written and oral communication of scientific results. Participating students worked roughly 10 hours per week during the academic year and 8 full time weeks during the summer. Our outcomes included 3 student publications and over 40 student conference presentations. Through the REU activities we promoted learning in both theoretical and applied contexts and enhanced the future workforce.
