Search

Computational prediction of 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., 20 pages, 15 figures

RuleDSD is a tool to support the rule-based modelling and simulation of DNA Strand Displacement (DSD) systems. It constitutes a software pipeline programmed in Python and integrated with PySB, a standard framework for rule-based modelling of biochemical systems. The input to Ru1eDSD is a domain-level model of a DSD system, where each initial DNA complex is described at the level of named pairing domains. The Ru1eDSD pipeline converts these domain-level descriptions into a canonical graph representation, and based on this performs a full state-space enumeration of DNA species reachable by applying the basic rules of DNA strand displacement reactions to the ensemble of initial species. The resulting chemical reaction network is then converted into a BioNetGen model and imported into the PySB framework for deterministic or stochastic simulation and analysis. Altogether, Ru1eDSD thus provides a customised front-end for rule-based modelling and simulation of DNA Strand Displacement systems using the BioNetGen simulation engine, and opens up further possibilities for harnessing the well-established rule-based model ling methods and tools that can easily be utilised through the PySB wrapper.

Barcoded DNA polony amplification techniques provide a means to impart a unique sequence identity onto specific locations of a surface wafer or chip. We describe a method whereby micro-scale 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 the use of conventional optics. The principle is based on the pair-wise association of uniquely tagged and spatially adjacenct polonies. The network of polonies connected by shared borders forms a graph whose topology can be reconstructed from a set of edges derived from pairs of barcodes associated with each other during a polony crosslinking phase, the sequences of which could be determined by isolation of the DNA and 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 partially stored and transmitted in the form of untethered graph topology. This effect may be exploited to form images by transferring molecular information from a surface of interest, which we demonstrated in silico by reconstructing images formed from stochastic transfer of hypothetical red, green, and blue molecular markers. The theory developed here could serve as a guide for a highly automated, multiplexable, and potentially super resolution imaging method based on molecular information encoding and transmission.

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; 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 random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density $\alpha$ exceeds a critical value $\alpha_s \approx 4.267$. However, rigorously proving the unsatisfiability of a given large 3-SAT instance is extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses) can in principle be constructed when the clause density $\alpha > 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 $\alpha$ scales at least linearly with the variable number $N$, but the focused local search algorithm works for clause densty $\alpha > c N^{b}$ with $b \approx 0.59$ and prefactor $c \approx 8$. The exponent $b$ can be further decreased by enlarging the single parameter $S$ of the focused local search algorithm., Comment: 9 pages, 7 figures included. Submitted to Physical Review E

We introduce a measure for the computational complexity of individual instances of a decision problern and study some of its properties. The inntance complexity of a string x with respect to a set A and time bound t, ic t(x : A), is defined as the size of the smallest special-case program for A that runs in time t, decides x correctly, and makes no mistakes on other strings ("don´t know" answers are permitted).

The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an exhaustive branch-and-bound algorithm to find tile sets of minimum cardinality for the PATS problem. Our algorithm makes use of a search tree in the lattice of partitions of the ambient rectangular grid, and an efficient bounding function to prune this search tree. Empirical data on the performance of the algorithm shows that it compares favourably to previously presented heuristic solutions to the problem., Comment: 12 pages, 6 figures

We consider the convergence behavior of a class of continuous-time dynamical systems corresponding to so-called symmetric Hopfield nets studied in neural networks theory. We prove that such systems may have transient times that are exponential in the system dimension (i.e. number of “neurons”), despite the fact that their dynamics are controlled by Liapunov functions. This result stands in contrast to many proposed uses of such systems in, e.g. combinatorial optimization applications, in which it is often implicitly assumed that their convergence is rapid. An additional interesting observation is that our example of an exponential-transient continuous-time system (a simulated binary counter) in fact converges more slowly than any discrete-time Hopfield system of the same representation size. This suggests that continuous-time systems may be worth investigating for gains in descriptional efficiency as compared to their discrete-time counterparts.

We prove that polynomial size discrete Hopfield networks with hidden units compute exactly the class of Boolean functions PSPACE/poly, i.e., the same functions as are computed by polynomial space-bounded nonuniform Turing machines. As a corollary to the construction, we observe also that networks with polynomially bounded interconnection weights compute exactly the class of functions P/poly, i.e., the class computed by polynomial time-bounded nonuniform Turing machines.

Non

Lynch (1975) has shown that every recursive set A not in P contains an infinite polynomial complexity core: a set of elements C ⊂ A such that any algorithm deciding A needs more than polynomial time almost everywhere on C. Actually, any A not in P contains infinitely many different cores, the collection of which forms a lattice under inclusion. We study the structure of this lattice, proving that, surprisingly, there are only three possibilities: assuming the lattice is not trivial (which happens if A is in P), its shape depends only on whether A is ‘almost P-immune’ or not. It is known that the natural intractable sets usually do not have this property.

We establish the truth of the "instance complexity conjecture" in the case of DEXT-complete sets w.r.t. polynomial time computations, and r.e. complete sets w.r.t. recursive computations. Specifically, we obtain for every DEXT-complete set A an exponentially dense subset C such that for every nondecreasing polynomial t(n)=/spl omega/(n log n), ic/sup t/(x:A)/spl ges/K/sup t/(x)-c holds for some constant c and all x/spl isin/C, where ic/sup t/ and K/sup t/ are the t-bounded instance complexity and Kolmogorov complexity measures, respectively. For r.e. complete sets A we obtain an infinite set C/spl sube/A~ such that ic/sup /spl infin(x:A)/spl ges/K/sup /spl infin(x)-c holds for some constant c and all x/spl isin/C. The proofs are based on the observation that Kolmogorov random strings are individually hard to recognize by bounded computations. >

Let A be a recursive problem not in P. Lynch has shown that A then has an infinite recursive polynomial complexity core. This is a collection C of instances of A such that every algorithm deciding A needs more than polynomial time almost everywhere on C. We investigate the complexity of recognizing the instances in such a core, and show that every recursive problem A not in P has an infinite core recognizable in subexponential time. We further study how dense the core sets for A can be, under various assumptions about the structure of A. Our main results in this direction are that if P ≠ NP, then NP-complete problems have polynomially nonsparse cores recognizable in subexponential time, and that EXPTIME-complete problems have cores of exponential density recognizable in exponential time.

A satisficing search problem consists of a set of probabilistic experiments to be performed in some order, seeking a satisfying configuration of successes and failures. The expected cost of the search depends both on the success probabilities of the individual experiments, and on the search strategy, which specifies the order in which the experiments are to be performed. A strategy that minimizes the expected cost is optimal. Earlier work has provided “optimizing functions” that compute optimal strategies for certain classes of search problems from the success probabilities of the individual experiments. We extend those results by providing a general model of such strategies, and an algorithm pao that identifies an approximately optimal strategy when the probability values are not known. The algorithm first estimates the relevant probabilities from a number of trials of each undetermined experiment, and then uses these estimates, and the proper optimizing function, to identify a strategy whose cost is, with high probability, close to optimal. We also show that if the search problem can be formulated as an and-or tree, then the pao algorithm can also “learn while doing”, i.e. gather the necessary statistics while performing the search.

The notion of “lowness” was introduced in computational complexity theory by Schoning [J, Comput. Systems Sci., 27 (1983), pp. 14–28] who studied sets in the class NP. This notion may be interpreted as setting an upper bound on the amount of information that can be encoded by a set. Here ideas from previous studies are incorporated in order to capture the notion of a set being exponentially low.The main result asserts the existence of a sparse set E such that ${\operatorname{DEXT}}(E) = {\operatorname{DEXT}}$, i.e., E is “exponentially low,” but E is not in the class P. In contrast, any set with small generalized Kolmogorov complexity that is exponentially low must be in the class P. In addition, we show that for each $k \geqq 2$, any sparse set S that is low with respect to the class $\Sigma _k^E $ of the exponential-time hierarchy (i.e., $\Sigma _k^E {(S) = \Sigma _k^E } $ ) must be in the class $\Sigma _k^P $ of the polynomial-time hierarchy. Similarly, for each $k \geqq 4$, any set with polynomial-siz...

This paper deals with the approximate string-matching problem with Hamming distance. The approximate string-matching with kmismatches problem is to find all locations at which a query of length m matches a factor of a text of length n with k or fewer mismatches. The approximate string-matching algorithms have both pleasing theoretical features, as well as direct applications, especially in computational biology. We consider a generalisation of this problem, the fixed-length approximate string-matching with k-mismatches problem: given a text t, a pattern x and an integer l, search for all the occurrences in t of all factors of x of length l with k or fewer mismatches with a factor of t. We present a practical parallel algorithm of comparable simplicity that requires only O(nm(l/w)/p) time, where w is the word size of the machine (e.g. 32 or 64 in practice) and p the number of processors. Thus the algorithm's performance is independent of k and the alphabet size |Σ|. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.