Inverse folding of RNA pseudoknot structures

Background  

RNA exhibits a variety of structural configurations. Here we consider a structure to be tantamount to the noncrossing Watson-Crick and G-U-base pairings (secondary structure) and additional cross-serial base pairs. These interactions are called pseudoknots and are observed across the whole spectrum of RNA functionalities. In the context of studying natural RNA structures, searching for new ribozymes and designing artificial RNA, it is of interest to find RNA sequences folding into a specific structure and to analyze their induced neutral networks. Since the established inverse folding algorithms, RNAinverse, RNA-SSD as well as INFO-RNA are limited to RNA secondary structures, we present in this paper the inverse folding algorithm Inv which can deal with 3-noncrossing, canonical pseudoknot structures.     

RNA folding on the 3D triangular lattice

Background  

Difficult problems in structural bioinformatics are often studied in simple exact models to gain insights and to derive general principles. Protein folding, for example, has long been studied in the lattice model. Recently, researchers have also begun to apply the lattice model to the study of RNA folding.     

An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding

Background

The basic RNA secondary structure prediction problem or single sequence folding problem (SSF) was solved 35 years ago by a now well-known \(O(n^3)\)-time dynamic programming method. Recently three methodologies—Valiant, Four-Russians, and Sparsification—have been applied to speedup RNA secondary structure prediction. The sparsification method exploits two properties of the input: the number of subsequence Z with the endpoints belonging to the optimal folding set and the maximum number base-pairs L. These sparsity properties satisfy \(0 \le L \le n / 2\) and \(n \le Z \le n^2 / 2\), and the method reduces the algorithmic running time to O(LZ). While the Four-Russians method utilizes tabling partial results.

Results

In this paper, we explore three different algorithmic speedups. We first expand the reformulate the single sequence folding Four-Russians \(\Theta \left(\frac{n^3}{\log ^2 n}\right)\)-time algorithm, to utilize an on-demand lookup table. Second, we create a framework that combines the fastest Sparsification and new fastest on-demand Four-Russians methods. This combined method has worst-case running time of \(O(\tilde{L}\tilde{Z})\), where \(\frac{{L}}{\log n} \le \tilde{L}\le min\left({L},\frac{n}{\log n}\right)\) and \(\frac{{Z}}{\log n}\le \tilde{Z} \le min\left({Z},\frac{n^2}{\log n}\right)\). Third we update the Four-Russians formulation to achieve an on-demand \(O( n^2/ \log ^2n )\)-time parallel algorithm. This then leads to an asymptotic speedup of \(O(\tilde{L}\tilde{Z_j})\) where \(\frac{{Z_j}}{\log n}\le \tilde{Z_j} \le min\left({Z_j},\frac{n}{\log n}\right)\) and \(Z_j\) the number of subsequence with the endpoint j belonging to the optimal folding set.

Conclusions

The on-demand formulation not only removes all extraneous computation and allows us to incorporate more realistic scoring schemes, but leads us to take advantage of the sparsity properties. Through asymptotic analysis and empirical testing on the base-pair maximization variant and a more biologically informative scoring scheme, we show that this Sparse Four-Russians framework is able to achieve a speedup on every problem instance, that is asymptotically never worse, and empirically better than achieved by the minimum of the two methods alone.

     

Graph-representation of oxidative folding pathways

Background  

The process of oxidative folding combines the formation of native disulfide bond with conformational folding resulting in the native three-dimensional fold. Oxidative folding pathways can be described in terms of disulfide intermediate species (DIS) which can also be isolated and characterized. Each DIS corresponds to a family of folding states (conformations) that the given DIS can adopt in three dimensions.     

Images de soustraction TEMP, en double isotope, Tc-sestamibi/I fusionnées au scanner : intérêt chez des patients présentant une hyperparathyroïdie

Purpose

To assess dual-tracer imaging of hybrid SPECT/CT (S/CT) compared to planar scintigraphy (S/PL) and ultrasounds (US), in preoperative localization hyperparathyroidism.

Methods

Dual tracer S/CT, S/PL and US for preoperative localization were performed in 99 patients with hyperparathyroidism. Patients with single-gland and multiple gland disease (MGD) were evaluated. For S/PL and S/CT, 15 MBq of ¹²³I were given and 2 hours later, 555 MBq/kg of ^99mTc-MIBI was injected. Images were acquired simultaneously using appropriate windows in S/PL and S/CT, then compared to US. Thus, the predicted positions were compared to the intraoperative findings and abnormal parathyroid glands were measured.

Results

Seventy-five patients underwent invasive surgery, which served as standard. Sixty-seven adenomas and 17 MGD were found on 70 patients. Sensitivity for US, S/PL and S/CT was respectively 69, 82 and 83%; and specificity was 96, 91 and 93% with an overall kappa-coefficient of 0.64, 0.73 and 0.76. US, S/PL and S/CT were correlated with the size of abnormal glands even if US remains the most accurate measuring technique. S/CT was able to predict the true position of the abnormal gland in 80% of cases.

Conclusion

Dual-isotope planar imaging and S/CT were statistically significantly superior to US imaging in sensitivity. The addition of CT to SPECT further improves parathyroid adenoma localization and predicts the size, which can help for mini-invasive surgery.     

An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem

Background  

The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including Monte Carlo methods, Evolutionary Algorithms, Tabu Search and hybrid approaches. In our work, we have introduced an ant colony optimisation (ACO) algorithm to address the non-deterministic polynomial-time hard (NP-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model – the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model.     

Design,implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics

Background  

The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n ⁶)time and O(n ⁴) space algorithm by Rivas and Eddy is currently the best available program.     

Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints

Background  

We are interested in the problem of predicting secondary structure for small sets of homologous RNAs, by incorporating limited comparative sequence information into an RNA folding model. The Sankoff algorithm for simultaneous RNA folding and alignment is a basis for approaches to this problem. There are two open problems in applying a Sankoff algorithm: development of a good unified scoring system for alignment and folding and development of practical heuristics for dealing with the computational complexity of the algorithm.     

Conservation of transition state structure in fast folding peripheral subunit-binding domains

Φ-Value analysis was used to characterise the structure of the transition state (TS) for folding of POB L146A Y166W, a peripheral subunit-binding domain that folds in microseconds. Helix 2 was structured in the TS with consolidating interactions from the structured loop that connects the two α-helices. This distribution of Φ-values was very similar to that determined for E3BD F166W, a homologue with high sequence and structural similarity. The extrapolated folding rate constants in water at 298 K were 210,000 s^− 1 for POB and 27,500 s^− 1 for E3BD. A contribution to the faster folding of POB came from its having significantly greater helical propensity in helix 2, the folding nucleus. The folding rate also appeared to be influenced by differences in the sequence and structural properties of the loop connecting the two helices. Unimodal downhill folding has been proposed as a conserved, biologically important property of peripheral subunit-binding domains. POB folds five times faster and E3BD folds slower than a proposed limit of 40,000 s^− 1 for barrier-limited folding. However, experimental evidence strongly suggests that both POB L146A Y166W and E3BD F166W fold in a barrier-limited process through a very similar TS ensemble.     

A simple, practical and complete O-time Algorithm for RNA folding using the Four-Russians Speedup

Background  

The problem of computationally predicting the secondary structure (or folding) of RNA molecules was first introduced more than thirty years ago and yet continues to be an area of active research and development. The basic RNA-folding problem of finding a maximum cardinality, non-crossing, matching of complimentary nucleotides in an RNA sequence of length n, has an O(n ³)-time dynamic programming solution that is widely applied. It is known that an o(n ³) worst-case time solution is possible, but the published and suggested methods are complex and have not been established to be practical. Significant practical improvements to the original dynamic programming method have been introduced, but they retain the O(n ³) worst-case time bound when n is the only problem-parameter used in the bound. Surprisingly, the most widely-used, general technique to achieve a worst-case (and often practical) speed up of dynamic programming, the Four-Russians technique, has not been previously applied to the RNA-folding problem. This is perhaps due to technical issues in adapting the technique to RNA-folding.     

Predicting protein folding pathways at the mesoscopic level based on native interactions between secondary structure elements

Background  

Since experimental determination of protein folding pathways remains difficult, computational techniques are often used to simulate protein folding. Most current techniques to predict protein folding pathways are computationally intensive and are suitable only for small proteins.     

Zinc induced folding is essential for TIM15 activity as an mtHsp70 chaperone

Background

TIM15/Zim17 in yeast and its mammalian ortholog Hep are Zn^2 + finger (Cys4) proteins that assist mtHsp70 in protein import into the mitochondrial matrix.

Methods

Here we characterized the Zn^2 + induced TIM15 folding integrating biophysical and computational approaches.

Results

TIM15 folding occurs from an essentially unstructured conformation to a Zn^2 +-coordinated protein in a fast and markedly temperature-dependent process. Moreover, we demonstrate unambiguously that Zn^2 + induced TIM15 folding is essential for its role as mtHsp70 chaperone since in the unstructured apo state TIM15 does not bind to mtHsp70 and is unable to prevent its aggregation. Molecular dynamics simulations help to understand the crucial role of Zn^2 + in promoting a stable and functional 3D architecture in TIM15. It is shown that the metal ion, through its coordinating cysteine residues, can mediate relevant long-range effects with the interaction interface for mtHsp70 coupling thus folding and function.

Conclusions

Zn^2 + induced TIM15 folding is essential for its function and likely occurs in mitochondrial matrix where high concentrations of Zn^2 + were reported.

General significance

The combination of experimental and computational approaches presented here provide an integrated structural, kinetic and thermodynamic view of the folding of a mitochondrial zinc finger protein, which might be relevant to understand the organelle import of proteins sharing this fold.     

Efficiently folding and circularly permuted variants of the Sapphire mutant of GFP

Background  

The green fluorescent protein (GFP) has been widely used in cell biology as a marker of gene expression, label of cellular structures, fusion tag or as a crucial constituent of genetically encoded biosensors. Mutagenesis of the wildtype gene has yielded a number of improved variants such as EGFP or colour variants suitable for fluorescence resonance energy transfer (FRET). However, folding of some of these mutants is still a problem when targeted to certain organelles or fused to other proteins.     

Nucleic acid chaperons: a theory of an RNA-assisted protein folding

Background  

Proteins are assumed to contain all the information necessary for unambiguous folding (Anfinsen's principle). However, ab initio structure prediction is often not successful because the amino acid sequence itself is not sufficient to guide between endless folding possibilities. It seems to be a logical to try to find the "missing" information in nucleic acids, in the redundant codon base.     

A replica exchange Monte Carlo algorithm for protein folding in the HP model

Background  

The ab initio protein folding problem consists of predicting protein tertiary structure from a given amino acid sequence by minimizing an energy function; it is one of the most important and challenging problems in biochemistry, molecular biology and biophysics. The ab initio protein folding problem is computationally challenging and has been shown to be -hard even when conformations are restricted to a lattice. In this work, we implement and evaluate the replica exchange Monte Carlo (REMC) method, which has already been applied very successfully to more complex protein models and other optimization problems with complex energy landscapes, in combination with the highly effective pull move neighbourhood in two widely studied Hydrophobic Polar (HP) lattice models.     

Evolutionary Pareto-optimization of stably folding peptides

Background  

As a rule, peptides are more flexible and unstructured than proteins with their substantial stabilizing hydrophobic cores. Nevertheless, a few stably folding peptides have been discovered. This raises the question whether there may be more such peptides that are unknown as yet. These molecules could be helpful in basic research and medicine.     

Measurement of the specific and non-specific binding energies of Mg2+ to RNA

Determining the non-specific and specific electrostatic contributions of magnesium binding to RNA is a challenging problem. We introduce a single-molecule method based on measuring the folding energy of a native RNA in magnesium and at its equivalent sodium concentration. The latter is defined so that the folding energy in sodium equals the non-specific electrostatic contribution in magnesium. The sodium equivalent can be estimated according to the empirical 100/1 rule (1 M NaCl is equivalent to 10 mM MgCl₂), which is a good approximation for most RNAs. The method is applied to an RNA three-way junction (3WJ) that contains specific Mg²⁺ binding sites and misfolds into a double hairpin structure without binding sites. We mechanically pull the RNA with optical tweezers and use fluctuation theorems to determine the folding energies of the native and misfolded structures in magnesium (10 mM MgCl₂) and at the equivalent sodium condition (1 M NaCl). While the free energies of the misfolded structure are equal in magnesium and sodium, they are not for the native structure, the difference being due to the specific binding energy of magnesium to the 3WJ, which equals $\text{Δ}G?$ 10 kcal/mol. Besides stabilizing the 3WJ, Mg²⁺ also kinetically rescues it from the misfolded structure over timescales of tens of seconds in a force-dependent manner. The method should generally be applicable to determine the specific binding energies of divalent cations to other tertiary RNAs.