Search for: All records

Wireframe DNA origami has emerged as a powerful approach to fabricating nearly arbitrary 2D and 3D geometries at the nanometer-scale. Complex scaffold and staple routing needed to design wireframe DNA origami objects, however, render fully automated, geometry-based sequence design approaches essential for their synthesis. And wireframe DNA origami structural fidelity can be limited by wireframe edges that are composed only of one or two duplexes. Here we introduce a fully automated computational approach that programs 2D wireframe origami assemblies using honeycomb edges composed of six parallel duplexes. These wireframe assemblies show enhanced structural fidelity from electron microscopy-based measurement of programmed angles compared with identical geometries programmed using dual-duplex edges. Molecular dynamics provides additional theoretical support for the enhanced structural fidelity observed. Application of our top-down sequence design procedure to a variety of complex objects demonstrates its broad utility for programmable 2D nanoscale materials.

 

For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph’s pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, ’85] and Feder [Feder, ’92] for pseudofactorization and factorization of unweighted graphs. We show that any n-vertex, m-edge graph with positive integer edge weights can be factored in O(m2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O(m2+n2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O(mn) time, plus the time to solve APSP, resulting in an O(mn + n2 log log n) running time. 

Abstract Wireframe DNA origami assemblies can now be programmed automatically from the top-down using simple wireframe target geometries, or meshes, in 2D and 3D, using either rigid, six-helix bundle (6HB) or more compliant, two-helix bundle (DX) edges. While these assemblies have numerous applications in nanoscale materials fabrication due to their nanoscale spatial addressability and high degree of customization, no easy-to-use graphical user interface software yet exists to deploy these algorithmic approaches within a single, standalone interface. Further, top-down sequence design of 3D DX-based objects previously enabled by DAEDALUS was limited to discrete edge lengths and uniform vertex angles, limiting the scope of objects that can be designed. Here, we introduce the open-source software package ATHENA with a graphical user interface that automatically renders single-stranded DNA scaffold routing and staple strand sequences for any target wireframe DNA origami using DX or 6HB edges, including irregular, asymmetric DX-based polyhedra with variable edge lengths and vertices demonstrated experimentally, which significantly expands the set of possible 3D DNA-based assemblies that can be designed. ATHENA also enables external editing of sequences using caDNAno, demonstrated using asymmetric nanoscale positioning of gold nanoparticles, as well as providing atomic-level models for molecular dynamics, coarse-grained dynamics with oxDNA, and other computational chemistry simulation approaches.