DNAforge: a design tool for nucleic acid wireframe nanostructures.

DNAforge is an online tool that provides a unified, user-friendly interface to several recent design methods for DNA and RNA wireframe nanostructures, with the possibility of integrating additional methods into the same framework. Currently, DNAforge supports three design methods for DNA nanostructures and two for RNA nanostructures. The tool enables the design, visualisation and sequence generation for highly complex wireframe nanostructures with a simple fully automated process. DNAforge is freely accessible at https://dnaforge.org/.

Algorithmic Design of 3D Wireframe RNA Polyhedra.

We address the problem of de novo design and synthesis of nucleic acid nanostructures, a challenge that has been considered in the area of DNA nanotechnology since the 1980s and more recently in the area of RNA nanotechnology. Toward this goal, we introduce a general algorithmic design process and software pipeline for rendering 3D wireframe polyhedral nanostructures in single-stranded RNA. To initiate the pipeline, the user creates a model of the desired polyhedron using standard 3D graphic design software. As its output, the pipeline produces an RNA nucleotide sequence whose corresponding RNA primary structure can be transcribed from a DNA template and folded in the laboratory. As case examples, we design and characterize experimentally three 3D RNA nanostructures: a tetrahedron, a triangular bipyramid, and a triangular prism. The design software is openly available and also provides an export of the targeted 3D structure into the oxDNA molecular dynamics simulator for easy simulation and visualization.

RNA secondary structure prediction with convolutional neural networks.

BACKGROUND: Predicting the secondary, i.e. base-pairing structure of a folded RNA strand is an important problem in synthetic and computational biology. First-principle algorithmic approaches to this task are challenging because existing models of the folding process are inaccurate, and even if a perfect model existed, finding an optimal solution would be in general NP-complete. RESULTS: In this paper, we propose a simple, yet effective data-driven approach. We represent RNA sequences in the form of three-dimensional tensors in which we encode possible relations between all pairs of bases in a given sequence. We then use a convolutional neural network to predict a two-dimensional map which represents the correct pairings between the bases. Our model achieves significant accuracy improvements over existing methods on two standard datasets, RNAStrAlign and ArchiveII, for 10 RNA families, where our experiments show excellent performance of the model across a wide range of sequence lengths. Since our matrix representation and post-processing approaches do not require the structures to be pseudoknot-free, we get similar good performance also for pseudoknotted structures. CONCLUSION: We show how to use an artificial neural network design to predict the structure for a given RNA sequence with high accuracy only by learning from samples whose native structures have been experimentally characterized, independent of any energy model.

Cotranscriptional Kinetic Folding of RNA Secondary Structures Including Pseudoknots.

Computational prediction of ribonucleic acid (RNA) structures is an important problem in computational structural biology. Studies of RNA structure formation often assume that the process starts from a fully synthesized sequence. Experimental evidence, however, has shown that RNA folds concurrently with its elongation. We investigate RNA secondary structure formation, including pseudoknots, that takes into account the cotranscriptional effects. We propose a single-nucleotide resolution kinetic model of the folding process of RNA molecules, where the polymerase-driven elongation of an RNA strand by a new nucleotide is included as a primitive operation, together with a stochastic simulation method that implements this folding concurrently with the transcriptional synthesis. Numerical case studies show that our cotranscriptional RNA folding model can predict the formation of conformations that are favored in actual biological systems. Our new computational tool can thus provide quantitative predictions and offer useful insights into the kinetics of RNA folding.

A computational framework for DNA sequencing microscopy.

We describe a method whereby microscale spatial information such as the relative positions of biomolecules on a surface can be transferred to a sequence-based format and reconstructed into images without conventional optics. Barcoded DNA "polymerase colony" (polony) amplification techniques enable one to distinguish specific locations of a surface by their sequence. Image formation is based on pairwise fusion of uniquely tagged and spatially adjacent polonies. The network of polonies connected by shared borders forms a graph whose topology can be reconstructed from pairs of barcodes fused during a polony cross-linking phase, the sequences of which are determined by recovery from the surface and next-generation (next-gen) sequencing. We developed a mathematical and computational framework for this principle called polony adjacency reconstruction for spatial inference and topology and show that Euclidean spatial data may be stored and transmitted in the form of graph topology. Images are formed by transferring molecular information from a surface of interest, which we demonstrated in silico by reconstructing images formed from stochastic transfer of hypothetical molecular markers. The theory developed here could serve as a basis for an automated, multiplexable, and potentially superresolution imaging method based purely on molecular information.

Effects of Design Choices on the Stiffness of Wireframe DNA Origami Structures.

DNA origami is a powerful method for the creation of 3D nanoscale objects, and in the past few years, interest in wireframe origami designs has increased due to their potential for biomedical applications. In DNA wireframe designs, the construction material is double-stranded DNA, which has a persistence length of around 50 nm. In this work, we study the effect of various design choices on the stiffness versus final size of nanoscale wireframe rods, given the constraints on origami designs set by the DNA origami scaffold size. An initial theoretical analysis predicts two competing mechanisms limiting rod stiffness, whose balancing results in an optimal edge length. For small edge lengths, the bending of the rod's overall frame geometry is the dominant factor, while the flexibility of individual DNA edges has a greater contribution at larger edge lengths. We evaluate our design choices through simulations and experiments and find that the stiffness of the structures increases with the number of sides in the cross-section polygon and that there are indications of an optimal member edge length. We also ascertain the effect of nicked DNA edges on the stiffness of the wireframe rods and demonstrate that ligation of the staple breakpoint nicks reduces the observed flexibility. Our simulations also indicate that the persistence length of wireframe DNA structures significantly decreases with increasing monovalent salt concentration.

Computer-Aided Production of Scaffolded DNA Nanostructures from Flat Sheet Meshes.

The use of DNA as a nanoscale construction material has been a rapidly developing field since the 1980s, in particular since the introduction of scaffolded DNA origami in 2006. Although software is available for DNA origami design, the user is generally limited to architectures where finding the scaffold path through the object is trivial. Herein, we demonstrate the automated conversion of arbitrary two-dimensional sheets in the form of digital meshes into scaffolded DNA nanostructures. We investigate the properties of DNA meshes based on three different internal frameworks in standard folding buffer and physiological salt buffers. We then employ the triangulated internal framework and produce four 2D structures with complex outlines and internal features. We demonstrate that this highly automated technique is capable of producing complex DNA nanostructures that fold with high yield to their programmed configurations, covering around 70 % more surface area than classic origami flat sheets.

DNA rendering of polyhedral meshes at the nanoscale.

It was suggested more than thirty years ago that Watson-Crick base pairing might be used for the rational design of nanometre-scale structures from nucleic acids. Since then, and especially since the introduction of the origami technique, DNA nanotechnology has enabled increasingly more complex structures. But although general approaches for creating DNA origami polygonal meshes and design software are available, there are still important constraints arising from DNA geometry and sense/antisense pairing, necessitating some manual adjustment during the design process. Here we present a general method of folding arbitrary polygonal digital meshes in DNA that readily produces structures that would be very difficult to realize using previous approaches. The design process is highly automated, using a routeing algorithm based on graph theory and a relaxation simulation that traces scaffold strands through the target structures. Moreover, unlike conventional origami designs built from close-packed helices, our structures have a more open conformation with one helix per edge and are therefore stable under the ionic conditions usually used in biological assays.

Witness of unsatisfiability for a random 3-satisfiability formula.

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density α exceeds a critical value α(s)≈4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density α>19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when α scales at least linearly with the variable number N, but the focused local search algorithm works for clause density α>cN(b) with b≈0.59 and prefactor c≈8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.

Circumspect descent prevails in solving random constraint satisfaction problems.

We study the performance of stochastic local search algorithms for random instances of the K-satisfiability (K-SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large K-SAT instances almost surely in linear time, up to high clause-to-variable ratios alpha; for example, for K = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.

General-purpose computation with neural networks: a survey of complexity theoretic results.

We survey and summarize the literature on the computational aspects of neural network models by presenting a detailed taxonomy of the various models according to their complexity theoretic characteristics. The criteria of classification include the architecture of the network (feedforward versus recurrent), time model (discrete versus continuous), state type (binary versus analog), weight constraints (symmetric versus asymmetric), network size (finite nets versus infinite families), and computation type (deterministic versus probabilistic), among others. The underlying results concerning the computational power and complexity issues of perceptron, radial basis function, winner-take-all, and spiking neural networks are briefly surveyed, with pointers to the relevant literature. In our survey, we focus mainly on the digital computation whose inputs and outputs are binary in nature, although their values are quite often encoded as analog neuron states. We omit the important learning issues.

Continuous-time symmetric Hopfield nets are computationally universal.

We establish a fundamental result in the theory of computation by continuous-time dynamical systems by showing that systems corresponding to so-called continuous-time symmetric Hopfield nets are capable of general computation. As is well known, such networks have very constrained Lyapunov-function controlled dynamics. Nevertheless, we show that they are universal and efficient computational devices, in the sense that any convergent synchronous fully parallel computation by a recurrent network of n discrete-time binary neurons, with in general asymmetric coupling weights, can be simulated by a symmetric continuous-time Hopfield net containing only 18n + 7 units employing the saturated-linear activation function. Moreover, if the asymmetric network has maximum integer weight size w(max) and converges in discrete time t*, then the corresponding Hopfield net can be designed to operate in continuous time Theta(t*/epsilon) for any epsilon > 0 such that w(max)2(12n)