Topological and Geometric Algorithms, Part I
Org: Mark Ellingham and Joanna Ellis-Monaghan
(Vanderbilt University and Saint Michael's College)
- JOANNA ELLIS-MONAGHAN, Saint Michael's College
New Dualities From Old: generating geometric, Petrie, and Wilson dualities and trialites of ribbon graphs [PDF]
We present twisted duality tools to identify and generate new graphs with various forms of self-duality including geometric duality, Petrie duality, Wilson duality, and both forms of triality. Previous work typically focused on regular maps, but the methods presented here apply to general embedded graphs. In contrast to the very large self-trial map of Wilson $(9,9)_9$, we show that there are self-trial graphs on as few as three edges. We reduce the search for graphs with some form of self-duality to the study of one vertex ribbon graphs, and we conclude with a fast algorithm that will find all graphs with any of the various forms of self-duality in the orbit of a graph that is isomorphic to any twisted dual of itself.
Joint work with Lowell Abrams, George Washington University
- CHRISTINE HEITSCH, Georgia Institute of Technology
Meanders and RNA Folding [PDF]
An RNA molecule is biochemical chain which folds in 3D via noncrossing base pairings called a secondary structure. Abstractly, two maximally different RNA secondary structures form a single closed loop known as a meander. Although meanders occur in a variety of mathematical settings, much remains unknown including their exact enumeration. Efforts to understand the geometry of RNA configuration landscapes lead naturally to a local move transformation on meanders. The resulting meander graphs have some interesting characteristics, which may yield new counting approaches. Additionally, MCMC sampling of meanders can provide insight into RNA branching configurations at viral genome length scales.
- NATAÅ A JONOSKA, University of South Florida
Topological graph theory in DNA self-assembly and DNA recombination [PDF]
DNA self-assembly of branched junction molecules as well as DNA origami can yield a variety of DNA based nanostructures such as spatial graphs and meshes. On the other side, natural template guided DNA recombination processes can be also modeled by four regular spatial graphs. In both cases, DNA structures can be represented as ribbon graphs (surfaces with boundaries) where the boundary components correspond to the DNA strands. Being able to experimentally address these strands can help to identify the structure. We address questions about the boundary components (DNA strands) that traverse such nano structures and their genus ranges.
- ADA MORSE, University of Vermont
DNA Origami and Knots in Graphs [PDF]
Motivated by the problem of determining unknotted routes for the scaffolding strand in DNA origami self-assembly, we examine existence and knottedness of A-trails in graphs embedded on surfaces in space. We construct infinite families of embedded graphs containing unknotted A-trails as well as infinite families containing no unknotted A-trails. While not every embedded Eulerian graph contains an unknotted A-trail, we conjecture that every abstract Eulerian graph has some embedding containing an unknotted A-trail. We prove this in the 4-regular case, giving an algorithm for finding such embeddings. Lastly, we discuss construction of knots using A-trails of rectangular grids.