Large deviations for random trees and the branching of RNA secondary structures.
Ontology highlight
ABSTRACT:
SUBMITTER: Bakhtin Y
PROVIDER: S-EPMC2834537 | biostudies-literature | 2009 Jan
REPOSITORIES: biostudies-literature
Publications
Large deviations for random trees and the branching of RNA secondary structures.
Bakhtin Yuri Y Heitsch Christine E CE
Bulletin of mathematical biology 20081213 1
We give a Large Deviation Principle (LDP) with explicit rate function for the distribution of vertex degrees in plane trees, a combinatorial model of RNA secondary structures. We calculate the typical degree distributions based on nearest neighbor free energies, and compare our results with the branching configurations found in two sets of large RNA secondary structures. We find substantial agreement overall, with some interesting deviations which merit further study. ...[more]
Similar Datasets
Project description:BackgroundIn several studies, secondary structures of ribosomal genes have been used to improve the quality of phylogenetic reconstructions. An extensive evaluation of the benefits of secondary structure, however, is lacking.ResultsThis is the first study to counter this deficiency. We inspected the accuracy and robustness of phylogenetics with individual secondary structures by simulation experiments for artificial tree topologies with up to 18 taxa and for divergency levels in the range of typical phylogenetic studies. We chose the internal transcribed spacer 2 of the ribosomal cistron as an exemplary marker region. Simulation integrated the coevolution process of sequences with secondary structures. Additionally, the phylogenetic power of marker size duplication was investigated and compared with sequence and sequence-structure reconstruction methods. The results clearly show that accuracy and robustness of Neighbor Joining trees are largely improved by structural information in contrast to sequence only data, whereas a doubled marker size only accounts for robustness.ConclusionsIndividual secondary structures of ribosomal RNA sequences provide a valuable gain of information content that is useful for phylogenetics. Thus, the usage of ITS2 sequence together with secondary structure for taxonomic inferences is recommended. Other reconstruction methods as maximum likelihood, bayesian inference or maximum parsimony may equally profit from secondary structure inclusion.ReviewersThis article was reviewed by Shamil Sunyaev, Andrea Tanzer (nominated by Frank Eisenhaber) and Eugene V. Koonin.Open peer reviewReviewed by Shamil Sunyaev, Andrea Tanzer (nominated by Frank Eisenhaber) and Eugene V. Koonin. For the full reviews, please go to the Reviewers' comments section.
| S-EPMC2821295 | biostudies-literature
Project description:Long RNA molecules are at the core of gene regulation across all kingdoms of life, while also serving as genomes in RNA viruses. Few studies have addressed the basic physical properties of long single-stranded RNAs. Long RNAs with nonrepeating sequences usually adopt highly ramified secondary structures and are better described as branched polymers. To test whether a branched polymer model can estimate the overall sizes of large RNAs, we employed fluorescence correlation spectroscopy to examine the hydrodynamic radii of a broad spectrum of biologically important RNAs, ranging from viral genomes to long noncoding regulatory RNAs. The relative sizes of long RNAs measured at low ionic strength correspond well to those predicted by two theoretical approaches that treat the effective branching associated with secondary structure formation-one employing the Kramers theorem for calculating radii of gyration, and the other featuring the metric of maximum ladder distance. Upon addition of multivalent cations, most RNAs are found to be compacted as compared with their original, low ionic-strength sizes. These results suggest that sizes of long RNA molecules are determined by the branching pattern of their secondary structures. We also experimentally validate the proposed computational approaches for estimating hydrodynamic radii of single-stranded RNAs, which use generic RNA structure prediction tools and thus can be universally applied to a wide range of long RNAs.
| S-EPMC5113152 | biostudies-literature
Project description:Many sociological theories make critically different macropredictions when their microassumptions are implemented stochastically rather than deterministically. Deviations from individuals' behavioral patterns described by microtheories can spark cascades that change macrooutcomes, even when deviations are rare and random. With two experiments, we empirically tested whether macrophenomena can be critically shaped by random deviations. Ninety-six percent of participants' decisions were in line with a deterministic theory of bounded rationality. Despite this impressive microlevel accuracy, the deterministic model failed to predict the observed macrooutcomes. However, a stochastic version of the same microtheory largely improved macropredictions. The stochastic model also correctly predicted the conditions under which deviations mattered. Results also supported the hypothesis that nonrandom deviations can result in fundamentally different macrooutcomes than random deviations. In conclusion, we echo the warning that deterministic microtheories can be misleading. Our findings show that taking into account deviations in sociological theories can improve explanations and predictions.
| S-EPMC7324148 | biostudies-literature
Project description:The family Picornaviridae contains important pathogens including, for example, hepatitis A virus and foot-and-mouth disease virus. The genome of these viruses is a single messenger-active (+)-RNA of 7200-8500 nt. Besides coding for the viral proteins, it also contains functionally important RNA secondary structures, among them an internal ribosomal entry site (IRES) region towards the 5'-end. This contribution provides a comprehensive computational survey of the complete genomic RNAs and a detailed comparative analysis of the conserved structural elements in seven of the currently nine genera in the family PICORNAVIRIDAE: Compared with previous studies we find: (i) that only smaller sections of the IRES region than previously reported are conserved at single base-pair resolution and (ii) that there is a number of significant structural elements in the coding region. Furthermore, we identify potential cis-acting replication elements in four genera where this feature has not been reported so far.
| S-EPMC97546 | biostudies-literature
Project description:BackgroundAccurate structure prediction methods play an important role for the understanding of RNA function. Energy-based, pseudoknot-free secondary structure prediction is one of the most widely used and versatile approaches, and improved methods for this task have received much attention over the past five years. Despite the impressive progress that as been achieved in this area, existing evaluations of the prediction accuracy achieved by various algorithms do not provide a comprehensive, statistically sound assessment. Furthermore, while there is increasing evidence that no prediction algorithm consistently outperforms all others, no work has been done to exploit the complementary strengths of multiple approaches.ResultsIn this work, we present two contributions to the area of RNA secondary structure prediction. Firstly, we use state-of-the-art, resampling-based statistical methods together with a previously published and increasingly widely used dataset of high-quality RNA structures to conduct a comprehensive evaluation of existing RNA secondary structure prediction procedures. The results from this evaluation clarify the performance relationship between ten well-known existing energy-based pseudoknot-free RNA secondary structure prediction methods and clearly demonstrate the progress that has been achieved in recent years. Secondly, we introduce AveRNA, a generic and powerful method for combining a set of existing secondary structure prediction procedures into an ensemble-based method that achieves significantly higher prediction accuracies than obtained from any of its component procedures.ConclusionsOur new, ensemble-based method, AveRNA, improves the state of the art for energy-based, pseudoknot-free RNA secondary structure prediction by exploiting the complementary strengths of multiple existing prediction procedures, as demonstrated using a state-of-the-art statistical resampling approach. In addition, AveRNA allows an intuitive and effective control of the trade-off between false negative and false positive base pair predictions. Finally, AveRNA can make use of arbitrary sets of secondary structure prediction procedures and can therefore be used to leverage improvements in prediction accuracy offered by algorithms and energy models developed in the future. Our data, MATLAB software and a web-based version of AveRNA are publicly available at http://www.cs.ubc.ca/labs/beta/Software/AveRNA.
| S-EPMC3750279 | biostudies-literature
Project description:BACKGROUND: Current RNA secondary structure prediction approaches predict prevalent pseudoknots such as the H-pseudoknot and kissing hairpin. The number of possible structures increases drastically when more complex pseudoknots are considered, thus leading to computational limitations. On the other hand, the enormous population of possible structures means not all of them appear in real RNA molecules. Therefore, it is of interest to understand how many of them really exist and the reasons for their preferred existence over the others, as any new findings revealed by this study might enhance the capability of future structure prediction algorithms for more accurate prediction of complex pseudoknots. METHODOLOGY/PRINCIPAL FINDINGS: A novel algorithm was devised to estimate the exact number of structural possibilities for a pseudoknot constructed with a specified number of base pair stems. Then, topological classification was applied to classify RNA pseudoknotted structures from data in the RNA STRAND database. By showing the vast possibilities and the real population, it is clear that most of these plausible complex pseudoknots are not observed. Moreover, from these classified motifs that exist in nature, some features were identified for further investigation. It was found that some features are related to helical stacking. Other features are still left open to discover underlying tertiary interactions. CONCLUSIONS: Results from topological classification suggest that complex pseudoknots are usually some well-known motifs that are themselves complex or the interaction results of some special motifs. Heuristics can be proposed to predict the essential parts of these complex motifs, even if the required thermodynamic parameters are currently unknown.
| S-EPMC3390330 | biostudies-literature
Project description:MOTIVATION: RNA secondary structure contains many non-canonical base pairs of different pair families. Successful prediction of these structural features leads to improved secondary structures with applications in tertiary structure prediction and simultaneous folding and alignment. RESULTS: We present a theoretical model capturing both RNA pair families and extended secondary structure motifs with shared nucleotides using 2-diagrams. We accompany this model with a number of programs for parameter optimization and structure prediction. AVAILABILITY: All sources (optimization routines, RNA folding, RNA evaluation, extended secondary structure visualization) are published under the GPLv3 and available at www.tbi.univie.ac.at/software/rnawolf/.
| S-EPMC3117358 | biostudies-literature
Project description:A class of wedge-shaped small molecules has been designed, synthesized, and shown to bind bulged RNA secondary structures. These minimally cationic ligands exhibit good affinity and selectivity for certain RNA bulges as demonstrated in a fluorescent intercalator displacement assay.
| S-EPMC4975938 | biostudies-literature
Project description:Detection of RNA structure similarities is still one of the major computational problems in the discovery of RNA functions. A case in point is the study of the new appreciated long non-coding RNAs (lncRNAs), emerging as new players involved in many cellular processes and molecular interactions. Among several mechanisms of action, some lncRNAs show specific substructures that are likely to be instrumental for their functioning. For instance, it has been reported in literature that some lncRNAs have a guiding or scaffolding role by binding chromatin-modifying protein complexes. Thus, a functionally characterized lncRNA (reference) can be used to infer the function of others that are functionally unknown (target), based on shared structural motifs.In our previous work we presented a tool, MONSTER v1.0, able to identify structural motifs shared between two full-length RNAs. Our procedure is mainly composed of two ad-hoc developed algorithms: nbRSSP_extractor for characterizing the folding of an RNA sequence by means of a sequence-structure descriptor (i.e., an array of non-overlapping substructures located on the RNA sequence and coded by dot-bracket notation); and SSD_finder, to enable an effective search engine for groups of matches (i.e., chains) common to the reference and target RNA based on a dynamic programming approach with a new score function. Here, we present an updated version of the previous one (MONSTER v1.1) accounting for the peculiar feature of lncRNAs that are not expected to have a unique fold, but appear to fluctuate among a large number of equally-stable folds. In particular, we improved our SSD_finder algorithm in order to take into account all the alternative equally-stable structures.We present an application of MONSTER v1.1 on lincRNAs, which are a specific class of lncRNAs located in genomic regions which do not overlap protein-coding genes. In particular, we provide reliable predictions of the shared chains between HOTAIR, ANRIL and COLDAIR. The latter are lincRNAs which interact with the same protein complexes of the Polycomb group and hence they are expected to share structural motifs.
| S-EPMC4460781 | biostudies-literature
Project description:The IS 200 transposase, a 16 kDa polypeptide encoded by the single open reading frame (ORF) of the insertion element, has been identified using an expression system based on T7 RNA polymerase. In wild-type IS 200, two sets of internal inverted repeats that generate RNA secondary structures provide two independent mechanisms for repression of transposase synthesis. The inverted repeat located near the left end of IS 200 is a transcriptional terminator that terminates read-through transcripts before they reach the IS 200 ORF. The terminator is functional in both directions and may terminate >80% of transcripts. Another control operates at the translational level: transposase synthesis is inhibited by occlusion of the ribosome-binding site (RBS) of the IS 200 ORF. The RBS (5'-AGGGG-3') is occluded by formation of a mRNA stem-loop structure whose 3' end is located only 3 nt upstream of the start codon. This mechanism reduces transposase synthesis approximately 10-fold. Primer extension experiments with AMV reverse transcriptase have provided evidence that this stem-loop RNA structure is actually formed. Tight repression of transposase synthesis, achieved through synergistic mechanisms of negative control, may explain the unusually low transposition frequency of IS 200.
| S-EPMC148624 | biostudies-other