Dataset Information

Computing the partition function for kinetically trapped RNA secondary structures.

ABSTRACT: An RNA secondary structure is locally optimal if there is no lower energy structure that can be obtained by the addition or removal of a single base pair, where energy is defined according to the widely accepted Turner nearest neighbor model. Locally optimal structures form kinetic traps, since any evolution away from a locally optimal structure must involve energetically unfavorable folding steps. Here, we present a novel, efficient algorithm to compute the partition function over all locally optimal secondary structures of a given RNA sequence. Our software, RNAlocopt runs in O(n3) time and O(n2) space. Additionally, RNAlocopt samples a user-specified number of structures from the Boltzmann subensemble of all locally optimal structures. We apply RNAlocopt to show that (1) the number of locally optimal structures is far fewer than the total number of structures--indeed, the number of locally optimal structures approximately equal to the square root of the number of all structures, (2) the structural diversity of this subensemble may be either similar to or quite different from the structural diversity of the entire Boltzmann ensemble, a situation that depends on the type of input RNA, (3) the (modified) maximum expected accuracy structure, computed by taking into account base pairing frequencies of locally optimal structures, is a more accurate prediction of the native structure than other current thermodynamics-based methods. The software RNAlocopt constitutes a technical breakthrough in our study of the folding landscape for RNA secondary structures. For the first time, locally optimal structures (kinetic traps in the Turner energy model) can be rapidly generated for long RNA sequences, previously impossible with methods that involved exhaustive enumeration. Use of locally optimal structure leads to state-of-the-art secondary structure prediction, as benchmarked against methods involving the computation of minimum free energy and of maximum expected accuracy. Web server and source code available at http://bioinformatics.bc.edu/clotelab/RNAlocopt/.

SUBMITTER: Lorenz WA

PROVIDER: S-EPMC3030561 | biostudies-literature | 2011

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Computing the partition function for kinetically trapped RNA secondary structures.

Lorenz William A WA Clote Peter P

PloS one 20110128 1

An RNA secondary structure is locally optimal if there is no lower energy structure that can be obtained by the addition or removal of a single base pair, where energy is defined according to the widely accepted Turner nearest neighbor model. Locally optimal structures form kinetic traps, since any evolution away from a locally optimal structure must involve energetically unfavorable folding steps. Here, we present a novel, efficient algorithm to compute the partition function over all locally o ...[more]

PMID: 21297972

Similar Datasets

Project description:In the present work, the conformational dynamics and folding pathways of i-motif DNA were studied in solution and in the gas-phase as a function of the solution pH conditions using circular dichroism (CD), photoacoustic calorimetry analysis (PAC), trapped ion mobility spectrometry-mass spectrometry (TIMS-MS), and molecular dynamics (MD). Solution studies showed at thermodynamic equilibrium the existence of a two-state folding mechanism, whereas during the pH = 7.0 → 4.5 transition a fast and slow phase (ΔHfast + ΔHslow = 43 ± 7 kcal mol-1) with a volume change associated with the formation of hemiprotonated cytosine base pairs and concomitant collapse of the i-motif oligonucleotide into a compact conformation were observed. TIMS-MS experiments showed that gas-phase, kinetically trapped i-motif DNA intermediates produced by nanoESI are preserved, with relative abundances depending on the solution pH conditions. In particular, a folded i-motif DNA structure was observed in nanoESI-TIMS-MS for low charge states in both positive and negative ion mode (e.g., z = ±3 to ±5) at low pH conditions. As solution pH increases, the cytosine neutralization leads to the loss of cytosine-cytosine+ (C·CH+) base pairing in the CCC strands and in those conditions we observe partially unfolded i-motif DNA conformations in nanoESI-TIMS-MS for higher charge states (e.g., z = -6 to -9). Collisional induced activation prior to TIMS-MS showed the existence of multiple local free energy minima, associated with the i-motif DNA unfolding at z = -6 charge state. For the first time, candidate gas-phase structures are proposed based on mobility measurements of the i-motif DNA unfolding pathway. Moreover, the inspection of partially unfolded i-motif DNA structures (z = -7 and z = -8 charge states) showed that the presence of inner cations may or may not induce conformational changes in the gas-phase. For example, incorporation of ammonium adducts does not lead to major conformational changes while sodium adducts may lead to the formation of sodium mediated bonds between two negatively charged sides inducing the stabilization towards more compact structures in new local, free energy minima in the gas-phase.

Project description:Retroviral virions initially assemble in an immature form that differs from that of the mature infectious particle. The RNA genomes in both immature and infectious particles are dimers, and interactions between the RNA dimer and the viral Gag protein ensure selective packaging into nascent immature virions. We used high-sensitivity selective 2'-hydroxyl acylation analyzed by primer extension (SHAPE) to obtain nucleotide-resolution structural information from scarce, femtomole quantities of Moloney murine leukemia virus (MuLV) RNA inside authentic virions and from viral RNA extracted from immature (protease-minus) virions. Our secondary structure model of the dimerization and packaging domain indicated that a stable intermolecular duplex known as PAL2, previously shown to be present in mature infectious MuLV particles, was sequestered in an alternate stem-loop structure inside immature virions. The intermediate state corresponded closely to a late-folding intermediate that we detected in time-resolved studies of the free MuLV RNA, suggesting that the immature RNA structure reflects trapping of the intermediate folding state by interactions in the immature virion. We propose models for the RNA-protein interactions that trap the RNA in the immature state and for the conformational rearrangement that occurs during maturation of virion particles.The structure of the RNA genome in mature retroviruses has been studied extensively, whereas very little was known about the RNA structure in immature virions. The immature RNA structure is important because it is the form initially selected for packaging in new virions and may have other roles. This lack of information was due to the difficulty of isolating sufficient viral RNA for study. In this work, we apply a high-sensitivity and nucleotide-resolution approach to examine the structure of the dimerization and packaging domain of Moloney murine leukemia virus. We find that the genomic RNA is packaged in a high-energy state, suggesting that interactions within the virion hold or capture the RNA before it reaches its most stable state. This new structural information makes it possible to propose models for the conformational changes in the RNA genome that accompany retroviral maturation.

Project description:BackgroundComputing the distance between two RNA secondary structures can contribute in understanding the functional relationship between them. When used repeatedly, such a procedure may lead to finding a query RNA structure of interest in a database of structures. Several methods are available for computing distances between RNAs represented as strings or graphs, but none utilize the RNA representation with dot plots. Since dot plots are essentially digital images, there is a clear motivation to devise an algorithm for computing the distance between dot plots based on image processing methods.ResultsWe have developed a new metric dubbed 'DoPloCompare', which compares two RNA structures. The method is based on comparing dot plot diagrams that represent the secondary structures. When analyzing two diagrams and motivated by image processing, the distance is based on a combination of histogram correlations and a geometrical distance measure. We introduce, describe, and illustrate the procedure by two applications that utilize this metric on RNA sequences. The first application is the RNA design problem, where the goal is to find the nucleotide sequence for a given secondary structure. Examples where our proposed distance measure outperforms others are given. The second application locates peculiar point mutations that induce significant structural alternations relative to the wild type predicted secondary structure. The approach reported in the past to solve this problem was tested on several RNA sequences with known secondary structures to affirm their prediction, as well as on a data set of ribosomal pieces. These pieces were computationally cut from a ribosome for which an experimentally derived secondary structure is available, and on each piece the prediction conveys similarity to the experimental result. Our newly proposed distance measure shows benefit in this problem as well when compared to standard methods used for assessing the distance similarity between two RNA secondary structures.ConclusionInspired by image processing and the dot plot representation for RNA secondary structure, we have managed to provide a conceptually new and potentially beneficial metric for comparing two RNA secondary structures. We illustrated our approach on the RNA design problem, as well as on an application that utilizes the distance measure to detect conformational rearranging point mutations in an RNA sequence.

Project description:HighlightsDNA kinking is inevitable for the highly anisotropic 1D-1D electrostatic interaction with the one-dimensionally periodically charged surface. The double helical structure of the DNA kinetically trapped on positively charged monomolecular films comprising the lamellar templates is strongly laterally stressed and extremely perturbed at the nanometer scale. The DNA kinetic trapping is not a smooth 3D-> 2D conformational flattening but is a complex nonlinear in-plane mechanical response (bending, tensile and unzipping) driven by the physics beyond the scope of the applicability of the linear worm-like chain approximation. Up to now, the DNA molecule adsorbed on a surface was believed to always preserve its native structure. This belief implies a negligible contribution of lateral surface forces during and after DNA adsorption although their impact has never been elucidated. High-resolution atomic force microscopy was used to observe that stiff DNA molecules kinetically trapped on monomolecular films comprising one-dimensional periodically charged lamellar templates as a single layer or as a sublayer are oversaturated by sharp discontinuous kinks and can also be locally melted and supercoiled. We argue that kink/anti-kink pairs are induced by an overcritical lateral bending stress (> 30 pNnm) inevitable for the highly anisotropic 1D-1D electrostatic interaction of DNA and underlying rows of positive surface charges. In addition, the unexpected kink-inducing mechanical instability in the shape of the template-directed DNA confined between the positively charged lamellar sides is observed indicating the strong impact of helicity. The previously reported anomalously low values of the persistence length of the surface-adsorbed DNA are explained by the impact of the surface-induced low-scale bending. The sites of the local melting and supercoiling are convincingly introduced as other lateral stress-induced structural DNA anomalies by establishing a link with DNA high-force mechanics. The results open up the study in the completely unexplored area of the principally anomalous kinetically trapped DNA surface conformations in which the DNA local mechanical response to the surface-induced spatially modulated lateral electrostatic stress is essentially nonlinear. The underlying rich and complex in-plane nonlinear physics acts at the nanoscale beyond the scope of applicability of the worm-like chain approximation.

Project description:BackgroundRNA performs many diverse functions in the cell in addition to its role as a messenger of genetic information. These functions depend on its ability to fold to a unique three-dimensional structure determined by the sequence. The conformation of RNA is in part determined by its secondary structure, or the particular set of contacts between pairs of complementary bases. Prediction of the secondary structure of RNA from its sequence is therefore of great interest, but can be computationally expensive. In this work we accelerate computations of base-pair probababilities using parallel graphics processing units (GPUs).ResultsCalculation of the probabilities of base pairs in RNA secondary structures using nearest-neighbor standard free energy change parameters has been implemented using CUDA to run on hardware with multiprocessor GPUs. A modified set of recursions was introduced, which reduces memory usage by about 25%. GPUs are fastest in single precision, and for some hardware, restricted to single precision. This may introduce significant roundoff error. However, deviations in base-pair probabilities calculated using single precision were found to be negligible compared to those resulting from shifting the nearest-neighbor parameters by a random amount of magnitude similar to their experimental uncertainties. For large sequences running on our particular hardware, the GPU implementation reduces execution time by a factor of close to 60 compared with an optimized serial implementation, and by a factor of 116 compared with the original code.ConclusionsUsing GPUs can greatly accelerate computation of RNA secondary structure partition functions, allowing calculation of base-pair probabilities for large sequences in a reasonable amount of time, with a negligible compromise in accuracy due to working in single precision. The source code is integrated into the RNAstructure software package and available for download at http://rna.urmc.rochester.edu.

Dataset Information

Computing the partition function for kinetically trapped RNA secondary structures.

Publications

Computing the partition function for kinetically trapped RNA secondary structures.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets