Vienna RNA Package software Kinfold implements the Gillespie algorithm for RNA secondary structure folding kinetics, for the move sets MS1 [resp. MS2], consisting of base pair additions and removals [resp. base pair addition, removals and shifts]. In this paper, for arbitrary secondary structures s, t of a given RNA sequence, we present the first optimal algorithm to compute the shortest MS2 folding trajectory s = s0, s1, . . . , sm = t, where each intermediate structure si+1 is obtained from its predecessor by the addition, removal or shift of a single base pair. The shortest MS1 trajectory between s and t is trivially equal to the number of base pairs belonging to s but not t, plus the number of base pairs belonging to t but not s. Our optimal algorithm applies integer programming (IP) to solve (essentially) the minimum feedback vertex set (FVS) problem for the "conflict digraph" associated with input secondary structures s, t, and then applies topological sort, in order to generate an optimal MS2 folding pathway from s to t that maximizes the use of shift moves. Since the optimal algorithm may require excessive run time, we also sketch a fast, near-optimal algorithm (details to appear elsewhere). Software for our algorithm will be publicly available at http://bioinformatics.bc.edu/clotelab/MS2distance/.

MOTIVATION: RNA thermometers (RNATs) are cis-regulatory elements that change secondary structure upon temperature shift. Often involved in the regulation of heat shock, cold shock and virulence genes, RNATs constitute an interesting potential resource in synthetic biology, where engineered RNATs could prove to be useful tools in biosensors and conditional gene regulation. RESULTS: Solving the 2-temperature inverse folding problem is critical for RNAT engineering. Here we introduce RNAiFold2T, the first Constraint Programming (CP) and Large Neighborhood Search (LNS) algorithms to solve this problem. Benchmarking tests of RNAiFold2T against existent programs (adaptive walk and genetic algorithm) inverse folding show that our software generates two orders of magnitude more solutions, thus allowing ample exploration of the space of solutions. Subsequently, solutions can be prioritized by computing various measures, including probability of target structure in the ensemble, melting temperature, etc. Using this strategy, we rationally designed two thermosensor internal ribosome entry site (thermo-IRES) elements, whose normalized cap-independent translation efficiency is approximately 50% greater at 42 °C than 30 °C, when tested in reticulocyte lysates. Translation efficiency is lower than that of the wild-type IRES element, which on the other hand is fully resistant to temperature shift-up. This appears to be the first purely computational design of functional RNA thermoswitches, and certainly the first purely computational design of functional thermo-IRES elements. AVAILABILITY: RNAiFold2T is publicly available as part of the new release RNAiFold3.0 at https://github.com/clotelab/RNAiFold and http://bioinformatics.bc.edu/clotelab/RNAiFold, which latter has a web server as well. The software is written in C ++ and uses OR-Tools CP search engine. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Retroviruses transcribe messenger RNA for the overlapping Gag and Gag-Pol polyproteins, by using a programmed -1 ribosomal frameshift which requires a slippery sequence and an immediate downstream stem-loop secondary structure, together called frameshift stimulating signal (FSS). It follows that the molecular evolution of this genomic region of HIV-1 is highly constrained, since the retroviral genome must contain a slippery sequence (sequence constraint), code appropriate peptides in reading frames 0 and 1 (coding requirements), and form a thermodynamically stable stem-loop secondary structure (structure requirement). RESULTS: We describe a unique computational tool, RNAsampleCDS, designed to compute the number of RNA sequences that code two (or more) peptides p,q in overlapping reading frames, that are identical (or have BLOSUM/PAM similarity that exceeds a user-specified value) to the input peptides p,q. RNAsampleCDS then samples a user-specified number of messenger RNAs that code such peptides; alternatively, RNAsampleCDS can exactly compute the position-specific scoring matrix and codon usage bias for all such RNA sequences. Our software allows the user to stipulate overlapping coding requirements for all 6 possible reading frames simultaneously, even allowing IUPAC constraints on RNA sequences and fixing GC-content. We generalize the notion of codon preference index (CPI) to overlapping reading frames, and use RNAsampleCDS to generate control sequences required in the computation of CPI. Moreover, by applying RNAsampleCDS, we are able to quantify the extent to which the overlapping coding requirement in HIV-1 [resp. HCV] contribute to the formation of the stem-loop [resp. double stem-loop] secondary structure known as the frameshift stimulating signal. Using our software, we confirm that certain experimentally determined deleterious HCV mutations occur in positions for which our software RNAsampleCDS and RNAiFold both indicate a single possible nucleotide. We generalize the notion of codon preference index (CPI) to overlapping coding regions, and use RNAsampleCDS to generate control sequences required in the computation of CPI for the Gag-Pol overlapping coding region of HIV-1. These applications show that RNAsampleCDS constitutes a unique tool in the software arsenal now available to evolutionary biologists. CONCLUSION: Source code for the programs and additional data are available at http://bioinformatics.bc.edu/clotelab/RNAsampleCDS/ .

Abstract Background RNA inverse folding is the problem of finding one or more sequences that fold into a user-specified target structure s0, i.e. whose minimum free energy secondary structure is identical to the target s0. Here we consider the ensemble of all RNA sequences that have low free energy with respect to a given target s0. Results We introduce the program , which computes the dual partition functionZ∗, defined as the sum of Boltzmann factors exp(−E(a,s0)/RT) of all RNA nucleotide sequences a compatible with target structure s0. Using , we efficiently sample RNA sequences that approximately fold into s0, where additionally the user can specify IUPAC sequence constraints at certain positions, and whether to include dangles (energy terms for stacked, single-stranded nucleotides). Moreover, since we also compute the dual partition functionZ∗(k) over all sequences having GC-content k, the user can require that all sampled sequences have a precise, specified GC-content. Using Z∗, we compute the dual expected energy 〈E∗〉, and use it to show that natural RNAs from the 12.0 database have higher minimum free energy than expected, thus suggesting that functional RNAs are under evolutionary pressure to be only marginally thermodynamically stable. We show that C. elegans precursor microRNA (pre-miRNA) is significantly non-robust with respect to mutations, by comparing the robustness of each wild type pre-miRNA sequence with 2000 [resp. 500] sequences of the same GC-content generated by , which approximately [resp. exactly] fold into the wild type target structure. We confirm and strengthen earlier findings that precursor microRNAs and bacterial small noncoding RNAs display plasticity, a measure of structural diversity. Conclusion We describe , which rapidly computes the dual partition functionZ∗ and samples sequences having low energy with respect to a target structure, allowing sequence constraints and specified GC-content. Using different inverse folding software, another group had earlier shown that pre-miRNA is mutationally robust, even controlling for compositional bias. Our opposite conclusion suggests a cautionary note that computationally based insights into molecular evolution may heavily depend on the software used. C/C++-software for is available at http://bioinformatics.bc.edu/clotelab/RNAdualPF .

BACKGROUND: Since RNA molecules regulate genes and control alternative splicing by allostery, it is important to develop algorithms to predict RNA conformational switches. Some tools, such as paRNAss, RNAshapes and RNAbor, can be used to predict potential conformational switches; nevertheless, no existent tool can detect general (i.e., not family specific) entire riboswitches (both aptamer and expression platform) with accuracy. Thus, the development of additional algorithms to detect conformational switches seems important, especially since the difference in free energy between the two metastable secondary structures may be as large as 15-20 kcal/mol. It has recently emerged that RNA secondary structure can be more accurately predicted by computing the maximum expected accuracy (MEA) structure, rather than the minimum free energy (MFE) structure. RESULTS: Given an arbitrary RNA secondary structure S₀ for an RNA nucleotide sequence a = a₁,..., a(n), we say that another secondary structure S of a is a k-neighbor of S₀, if the base pair distance between S₀ and S is k. In this paper, we prove that the Boltzmann probability of all k-neighbors of the minimum free energy structure S₀ can be approximated with accuracy ε and confidence 1 - p, simultaneously for all 0 ≤ k < K, by a relative frequency count over N sampled structures, provided that N>N(ε,p,K)=Φ⁻¹(p/2K)²/4ε², where Φ(z) is the cumulative distribution function (CDF) for the standard normal distribution. We go on to describe the algorithm RNAborMEA, which for an arbitrary initial structure S₀ and for all values 0 ≤ k < K, computes the secondary structure MEA(k), having maximum expected accuracy over all k-neighbors of S₀. Computation time is O(n³ · K²), and memory requirements are O(n² · K). We analyze a sample TPP riboswitch, and apply our algorithm to the class of purine riboswitches. CONCLUSIONS: The approximation of RNAbor by sampling, with rigorous bound on accuracy, together with the computation of maximum expected accuracy k-neighbors by RNAborMEA, provide additional tools toward conformational switch detection. Results from RNAborMEA are quite distinct from other tools, such as RNAbor, RNAshapes and paRNAss, hence may provide orthogonal information when looking for suboptimal structures or conformational switches. Source code for RNAborMEA can be downloaded from http://sourceforge.net/projects/rnabormea/ or http://bioinformatics.bc.edu/clotelab/RNAborMEA/.

Protein structure prediction is regarded as a highly challenging problem both for the biology and for the computational communities. In recent years, many approaches have been developed, moving to increasingly complex lattice models and off-lattice models. This paper presents a Large Neighborhood Search (LNS) to find the native state for the Hydrophobic-Polar (HP) model on the Face-Centered Cubic (FCC) lattice or, in other words, a self-avoiding walk on the FCC lattice having a maximum number of H-H contacts. The algorithm starts with a tabu-search algorithm, whose solution is then improved by a combination of constraint programming and LNS. The flexible framework of this hybrid algorithm allows an adaptation to the Miyazawa-Jernigan contact potential, in place of the HP model, thus suggesting its potential for tertiary structure prediction. Benchmarking statistics are given for our method against the hydrophobic core threading program HPstruct, an exact method which can be viewed as complementary to our method.

MOTIVATION: Thermodynamics-based dynamic programming RNA secondary structure algorithms have been of immense importance in molecular biology, where applications range from the detection of novel selenoproteins using expressed sequence tag (EST) data, to the determination of microRNA genes and their targets. Dynamic programming algorithms have been developed to compute the minimum free energy secondary structure and partition function of a given RNA sequence, the minimum free-energy and partition function for the hybridization of two RNA molecules, etc. However, the applicability of dynamic programming methods depends on disallowing certain types of interactions (pseudoknots, zig-zags, etc.), as their inclusion renders structure prediction an nondeterministic polynomial time (NP)-complete problem. Nevertheless, such interactions have been observed in X-ray structures. RESULTS: A non-Boltzmannian Monte Carlo algorithm was designed by Wang and Landau to estimate the density of states for complex systems, such as the Ising model, that exhibit a phase transition. In this article, we apply the Wang-Landau (WL) method to compute the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. Our method is shown to be much faster than existent software, such as RNAsubopt. From density of states, we compute the partition function over all secondary structures and over all pseudoknot-free hybridizations. The advantage of the WL method is that by adding a function to evaluate the free energy of arbitrary pseudoknotted structures and of arbitrary hybridizations, we can estimate thermodynamic parameters for situations known to be NP-complete. This extension to pseudoknots will be made in the sequel to this article; in contrast, the current article describes the WL algorithm applied to pseudoknot-free secondary structures and hybridizations. AVAILABILITY: The WL RNA hybridization web server is under construction at http://bioinformatics.bc.edu/clotelab/.

It is a classical result of Stein and Waterman that the asymptotic number S(n) of RNA secondary structures is 1.104366 ldr n-3/2ldr 2.618034n, where the combinatorial model of RNA concerns a length n homopolymer, such that any base can pair with any other base, subject to the usual convention that hairpin loops must contain at least thetas = 1 unpaired bases. The result of Stein and Waterman is proved by developing recursions,using generating functions and applying Bender's theorem. These recursions form the basis to compute the minimum free energy secondary structure for a given RNA sequence, with respect to the Nussinov energy model, later extended by Zuker to substantially more complicated resursions for the Turner nearest neighbor energy model. In this paper, we study combinatorial asymptotic for two special subclasses of RNA secondary structures - canonical and saturated structures. Canonical secondary structures are defined to have no lonely (isolated) base pairs. This class of secondary structures was introduced b y Bompfuenewerer et al., who noted that the runtime of Vienna RNA Package is substantially decreased when restricting computations to canonical structures. Here we provide an explanation for the speed-up, by proving that the asymptotic number of canonical RNA secondary structures is 2.1614 ldr n-3/2ldr 1.96798n. Saturated secondary structures have the property that no base pairs can be added without violating the definition of secondary structure (i.e. introducing a pseudoknotor base triple). In the Nussinov energy model,where the energy for a base pair is -1, saturated structures correspond to kinetic traps.n prior work, we showed that the asymptotic number of saturated structures of a length n homopolymer is 1.07427 ldr n-3/2ldr 2.35467n. In this paper, we show that the expected number of base pairs of random saturated structures, generated by a natural stochastic procedure, is (zthetas+1)/((1-z)2) (-z-Sigmai=0thetas(z2)/(i+1)) (int e (z+Sigmai=0thetas(z2)/(i+1))dz).

The diversity and importance of the role played by RNAs in the regulation and development of the cell are now well-known and well-documented. This broad range of functions is achieved through specific structures that have been (presumably) optimized through evolution. State-of-the-art methods, such as McCaskill's algorithm, use a statistical mechanics framework based on the computation of the partition function over the canonical ensemble of all possible secondary structures on a given sequence. Although secondary structure predictions from thermodynamics-based algorithms are not as accurate as methods employing comparative genomics, the former methods are the only available tools to investigate novel RNAs, such as the many RNAs of unknown function recently reported by the ENCODE consortium. In this paper, we generalize the McCaskill partition function algorithm to sum over the grand canonical ensemble of all secondary structures of all mutants of the given sequence. Specifically, our new program, RNAmutants, simultaneously computes for each integer k the minimum free energy structure MFE(k) and the partition function Z(k) over all secondary structures of all k-point mutants, even allowing the user to specify certain positions required not to mutate and certain positions required to base-pair or remain unpaired. This technically important extension allows us to study the resilience of an RNA molecule to pointwise mutations. By computing the mutation profile of a sequence, a novel graphical representation of the mutational tendency of nucleotide positions, we analyze the deleterious nature of mutating specific nucleotide positions or groups of positions. We have successfully applied RNAmutants to investigate deleterious mutations (mutations that radically modify the secondary structure) in the Hepatitis C virus cis-acting replication element and to evaluate the evolutionary pressure applied on different regions of the HIV trans-activation response element. In particular, we show qualitative agreement between published Hepatitis C and HIV experimental mutagenesis studies and our analysis of deleterious mutations using RNAmutants. Our work also predicts other deleterious mutations, which could be verified experimentally. Finally, we provide evidence that the 3' UTR of the GB RNA virus C has been optimized to preserve evolutionarily conserved stem regions from a deleterious effect of pointwise mutations. We hope that there will be long-term potential applications of RNAmutants in de novo RNA design and drug design against RNA viruses. This work also suggests potential applications for large-scale exploration of the RNA sequence-structure network. Binary distributions are available at http://RNAmutants.csail.mit.edu/.

MOTIVATION: We describe algorithms implemented in a new software package, RNAbor, to investigate structures in a neighborhood of an input secondary structure S of an RNA sequence s. The input structure could be the minimum free energy structure, the secondary structure obtained by analysis of the X-ray structure or by comparative sequence analysis, or an arbitrary intermediate structure. RESULTS: A secondary structure T of s is called a delta-neighbor of S if T and S differ by exactly delta base pairs. RNAbor computes the number (N(delta)), the Boltzmann partition function (Z(delta)) and the minimum free energy (MFE(delta)) and corresponding structure over the collection of all delta-neighbors of S. This computation is done simultaneously for all delta < or = m, in run time O (mn3) and memory O(mn2), where n is the sequence length. We apply RNAbor for the detection of possible RNA conformational switches, and compare RNAbor with the switch detection method paRNAss. We also provide examples of how RNAbor can at times improve the accuracy of secondary structure prediction. AVAILABILITY: http://bioinformatics.bc.edu/clotelab/RNAbor/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: A k-point mutant of a given RNA sequence s = s(1), ..., s(n) is an RNA sequence s' = s'(1),..., s'(n) obtained by mutating exactly k-positions in s; i.e. Hamming distance between s and s' equals k. To understand the effect of pointwise mutation in RNA, we consider the distribution of energies of all secondary structures of k-point mutants of a given RNA sequence. RESULTS: Here we describe a novel algorithm to compute the mean and standard deviation of energies of all secondary structures of k-point mutants of a given RNA sequence. We then focus on the tail of the energy distribution and compute, using the algorithm AMSAG, the k-superoptimal structure; i.e. the secondary structure of a < or =k-point mutant having least free energy over all secondary structures of all k'-point mutants of a given RNA sequence, for k' < or = k. Evidence is presented that the k-superoptimal secondary structure is often closer, as measured by base pair distance and two additional distance measures, to the secondary structure derived by comparative sequence analysis than that derived by the Zuker minimum free energy structure of the original (wild type or unmutated) RNA.

MOTIVATION: We describe a stand-alone algorithm to predict disulfide bond partners in a protein given only the amino acid sequence, using a novel neural network architecture (the diresidue neural network), and given input of symmetric flanking regions of N-terminus and C-terminus half-cystines augmented with residue secondary structure (helix, coil, sheet) as well as evolutionary information. The approach is motivated by the observation of a bias in the secondary structure preferences of free cysteines and half-cystines, and by promising preliminary results we obtained using diresidue position-specific scoring matrices. RESULTS: As calibrated by receiver operating characteristic curves from 4-fold cross-validation, our conditioning on secondary structure allows our novel diresidue neural network to perform as well as, and in some cases better than, the current state-of-the-art method. A slight drop in performance is seen when secondary structure is predicted rather than being derived from three-dimensional protein structures.

We generalize the familiar position-specific score matrix (PSSM), aka weight matrix, by considering a log-odds score for (nonadjacent) k-tuple frequencies, each k-tuple score weighted by the product of its mutual information and its statistical significance, as measured by a point estimator for the p-value of the mutual information. Performance of this new approach, along with other variants of generalized PSSM and profile methods, is measured by receiver-operating characteristic (ROC) curves for the specific problem of signal peptide cleavage site recognition. We additionally compare Vert's recent support vector machine string kernel, Brown's joint probability approximation algorithm and the method WAM. Similar algorithm comparisons are made, though not as extensively, in the case of disulfide bond recognition. While in the case of signal peptide cleavage site recognition, the monoresidue PSSM is essentially competitive, within the limits of statistical significance, even against Vert's support vector machine kernel, diresidue and triresidue PSSM methods display improved performance over monoresidue PSSM for disulfide bond recognition.

The primary aim of this paper is to introduce higher type analogues of some familiar parallel complexity classes, and to show that these higher type classes can be characterised in significantly different ways. Recursion-theoretic, proof-theoretic and machine-theoretic characterisations are given for various classes, providing evidence of their naturalness.>

The cutting planes refutation system for propositional logic is an extension of resolution and is based on showing the nonexistence of solutions for families of integer linear inequalities. The author defines a modified system of cutting planes with limited extension and shows that this system can polynomially simulate constant-depth Frege proof systems. The principal tool to establish this result is an effective version of cut elimination for modified cutting planes with limited extension. Thus, within a polynomial factor, one can simulate classical propositional logic proofs using modus ponens by refutation-style proofs, provided the formula depth is bounded by a constant. Propositional versions of the Paris-Harrington theorem, Kanamori-McAloon theorem, and variants are proposed as possible candidates for combinatorial tautologies that may require exponential-size cutting planes and Frege proofs.>

This paper studies the invariance groups ${\bf S}(f)$ of boolean functions $f \in {\bf B}_n $ (i.e., $f:\{ 0,1\} ^n \to \{ 0,1\} $) on n variables, i.e., the set of all permutations on n elements which leave f invariant. After building intuition by presenting several examples that suggest relations between algebraic properties of groups and computational complexity of languages, necessary and sufficient conditions are given via Pólya’s cycle index for an arbitrary finite permutation group to be of the form $S(f)$, for some $f \in {\bf B}_n $. It is shown that asymptotically “almost all” boolean functions have trivial invariance groups. For cyclic groups $G \leqq {\bf S}_n $ a logspace algorithm for determining whether the given group is of the form ${\bf S}(f)$, for some $f \in {\bf B}_n $ is given. The applicability of group theoretic techniques in the study of the parallel complexity of languages is demonstrated. For any language L let $L_n $ be the characteristic function of the set of all strings in L which have length exactly n and let ${\bf S}_n (L)$ be the invariance group of $L_n $. The index $| {{\bf S}_n :{\bf S}_n (L)} |$ are considered as a function of n and the class of languages whose index is polynomial in n is studied. Bochert’s lower bound on the index of primitive permutation groups is used together with the O’Nan-Scott theorem, a deep result in the classification of finite simple groups, in order to show that any language with polynomial index is in (nonuniform) ${\text{TC}}^0 $ and hence in (nonuniform) ${\text{NC}}^1 $. As a corollary, an extension is given of a result of Fagin–Klawe-Pippenger–Stockmeyer, giving necessary and sufficient conditions for a language with polynomial index to be computable by a constant depth polynomial size circuit family. As another corollary, it is shown that the problem of “weight-swapping” for a sequence of groups of polynomial index is in (nonuniform) ${\text{NC}}^1 $.

Using sequential, machine-independent characterizations of the parallel complexity classes AC/sup k/ and NC/sup k/, the author establishes a conjecture of S.A. Cook (1975) regarding polynomial size Frege proofs for a certain infinite family. A related result is established with constant formula-depth polynomial size Frege proofs for a system AV related to uniform AC/sup 0/ functions.>

Abstract We give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in eα if and only if there is a Turing machine which computes X and “halts” in less than or equal to the ordinal number ωα of steps. This result represents a generalization of the well-known “limit lemma” due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game A ⊆ ωω and the Turing degree of a winning strategy ƒ for one of the players—roughly, ƒ can be chosen to be recursive in 0α and this is the best possible (see §4 for precise results).

Abstract Solovay has shown that if F: [ω]ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0α, where α is a recursive ordinal, there is a clopen partition F: [ω]ω → 2 such that every infinite homogeneous set is Turing above 0α (an anti-basis result). Here we refine these results, by associating the “order type” of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem.

We give two new finite combinatorial statements which are independent of Peano arithmetic, using the methods of Kirby and Paris [6] and Paris [12]. Both are in fact equivalent over Peano arithmetic (denoted by P) to its 1-consistency. The first involves trees and the second linear orderings. Both were “motivated” by anti-basis theorems of Clote (cf. [1], [2]). The one involving trees, however, is not unrelated to the Kirby-Paris characterization of strong cuts in terms of the tree property [6], but, in fact, comes directly from König's lemma, of which it is a miniaturization. (See the remark preceding Theorem 3 below.) The resulting combinatorial statement is easily seen to imply the independent statement discovered by Mills [11], but it is not clear how to show their equivalence over Peano arithmetic without going through 1-consistency. The one involving linear orderings miniaturizes the property of infinite sets X that any linear ordering of X is isomorphic to ω or ω* on some infinite subset of X. Both statements are analogous to Example 2 of [12] and involve the notion of dense [12] or relatively large [14] finite set. We adopt the notations and definitions of [6] and [12]. We shall in particular have need of the notions of semiregular, regular and strong initial segments and of indicators.