Search

Funding Information: The research of A.E., A.M., and P.O. was supported by Academy of Finland grant 311639. A.K. and A.K.N. have been supported by Academy of Finland grant 308992. The research of I.K. was supported by Japan Society for the Promotion of Science (JSPS) Early-Career Scientists 18K18144, Fund for the Promotion of Joint International Research (B) 19KK0261, and Young Researcher Dispatch Program (School of Engineering, Tohoku University). The research of A.M. was additionally supported by NSF-DMS (grant numbers 1800443/1764366) and Nokia Foundation (2017). The research of Y.S. has been supported by JSPS Grant-in-Aid for Scientific Research (KAKENHI; grant numbers 18K19831 and 19H04201). The research of L.O. and F.C.S. was supported by European Research Council grant agreement no. 694410, project AEDNA. Publisher Copyright: © 2022 The Authors. Published by American Chemical Society. 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.

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.

VK: Orponen, P.; NC Due to its programmable nature, DNA nanotechnology is currently one of the most advanced and most reliable self-assembly-based methodologies for constructing molecular-scale structures and devices. This makes DNA nanotechnology a highly promising candidate for generating radically new manufacturing technologies. Our specific interest is in the use of DNA as a template and scaffold for the self-assembly of carbon-nanotube field effect transistor (CNFET) circuits. In this paper, we introduced a novel high-level design framework for self-assembling CNFET circuits. According to this methodology, the elements of the circuits, i.e., CNFETs and the connecting carbon nanotube wires, are affixed on different rectangular DNA scaffolds, called tiles, and self-assemble into the desired circuit. The introduced methodology presents several advantages, both at the design level, and for analyzing the reliability of these systems. We make use of these advantages and introduce a new fault-tolerant architecture for CNFET circuits. Then, we analyze its reliability both by computer simulations and by analytical methods.

VK: Orponen, P.; NC; TRITON It was suggested1 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 technique2, DNA nanotechnology has enabled increasingly more complex structures3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18. But although general approaches for creating DNA origami polygonal meshes and design software are available14,16,17,19,20,21, 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.

The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model., Comment: 1 + 36 pages, 18 figures. arXiv admin note: text overlap with arXiv:0911.2924

We consider the problem of gathering data from a wireless multi-hop network of energy-constrained sensor nodes to a common base station. Specifically, we aim to balance the total amount of data received from the sensor network during its lifetime against a requirement of sufficient coverage for all the sensor locations surveyed. Our main contribution lies in formulating this balanced data gathering task, studying the effects of balancing, and proposing an approximation algorithm for the problem. Based on an LP network flow formulation, we present experimental results on both optimal and approximate data routing designs, in open transmission ranges and with impenetrable obstacles between the nodes.

We study the precise conditions under which all optimization strategies for a given family of finite functions yield the same expected maximization performance, when averaged over a uniform distribution of the functions. In the case of bounded-length searches in a family of Boolean functions, we provide tight connections between such ''No Free Lunch'' conditions and the structure of t-designs and t-wise balanced designs for arbitrary values t. As a corollary, we obtain a nontrivial family of n-variate Boolean functions that satisfies the ''No Free Lunch'' condition with respect to searches of length @W(n^1^/^2/log^1^/^2n). Modifying the construction, we also obtain nontrivial ''No Free Lunch'' families of functions with large ranges.

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.

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.

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 wmaxand converges in discrete time t*, then the corresponding Hopfield net can be designed to operate in continuous time Θ(t*/ɛ) for any ɛ > 0 such that wmax212n≤ ɛ21/ɛ. In terms of standard discrete computation models, our result implies that any polynomially space-bounded Turing machine can be simulated by a family of polynomial-size continuous-time symmetric Hopfield nets.

A local search algorithm solving an NP-complete optimisation problem can be viewed as a stochastic process moving in an 'energy landscape' towards eventually finding an optimal solution. For the random 3-satisfiability problem, the heuristic of focusing the local moves on the presently unsatisfiedclauses is known to be very effective: the time to solution has been observed to grow only linearly in the number of variables, for a given clauses-to-variables ratio $\alpha$ sufficiently far below the critical satisfiability threshold $\alpha_c \approx 4.27$. We present numerical results on the behaviour of three focused local search algorithms for this problem, considering in particular the characteristics of a focused variant of the simple Metropolis dynamics. We estimate the optimal value for the ``temperature'' parameter $\eta$ for this algorithm, such that its linear-time regime extends as close to $\alpha_c$ as possible. Similar parameter optimisation is performed also for the well-known WalkSAT algorithm and for the less studied, but very well performing Focused Record-to-Record Travel method. We observe that with an appropriate choice of parameters, the linear time regime for each of these algorithms seems to extend well into ratios $\alpha > 4.2$ -- much further than has so far been generally assumed. We discuss the statistics of solution times for the algorithms, relate their performance to the process of ``whitening'', and present some conjectures on the shape of their computational phase diagrams., Comment: 20 pages, lots of figures