RUI: Collaborative Research: New Graph Theory from and for Nanoconstruct Design Strategies

Saint Michael'S College, Colchester VT

Investigators

Abstract

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