Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Sparsification of RNA structure prediction including pseudoknots
Mathias M?hl, Raheleh Salari, Sebastian Will, Rolf Backofen, S Cenk Sahinalp
Algorithms for Molecular Biology , 2010, DOI: 10.1186/1748-7188-5-39
Abstract: In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerich algorithm). In all algorithms the number of "candidate" substructures to be considered is reduced.Our experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation.Recently discovered catalytic and regulatory RNAs [1,2] exhibit their functionality due to specific secondary and tertiary structures [3,4]. The vast majority of computational analysis of non-coding RNAs have been restricted to nested secondary structures, neglecting pseudoknots - which are "among the most prevalent RNA structures" [5]. For example, Xaya-phoummine et al. [6] estimated that up to 30% of the base pairs in G+C-rich sequences form pseudoknots.However the general problem of pseudoknotted RNA structure prediction is NP-hard. As a result, a number of approaches have been introduced for handling restricted classes of pseudoknots [7-13]. Condon et al. [14] give an overview of their structure classes and the algorithm-specific restrictions and M?hl et al. [15] develop a general framework showing that all these algorithms follow a general scheme, which they use for efficient alignment of pseudoknotted RNA.The most general algorithm (with respect to the pseudoknot classes handled) among
Prediction for RNA planar pseudoknots
Li Hengwu,Zhu Daming,Liu Zhendong,Li Hong,
Li Hengwu
,Zhu Daming,Liu Zhendong and Li Hong

自然科学进展 , 2007,
Abstract: Based on m-stems and semi-extensible structure, a model is presented to represent RNA planar pseudoknots, and corresponding dynamic programming algorithm is designed and implemented to predict arbitrary planar pseudoknots and simple non-planar pseudoknots with O(n4) time and O(n3) space. The algorithm folds total 245 sequences in the Pseudobase database, and the test results indicate that the algorithm has good accuracy, sensitivity and specificity.
Prediction of RNA pseudoknots by Monte Carlo simulations  [PDF]
G. Vernizzi,H. Orland,A. Zee
Quantitative Biology , 2004,
Abstract: In this paper we consider the problem of RNA folding with pseudoknots. We use a graphical representation in which the secondary structures are described by planar diagrams. Pseudoknots are identified as non-planar diagrams. We analyze the non-planar topologies of RNA structures and propose a classification of RNA pseudoknots according to the minimal genus of the surface on which the RNA structure can be embedded. This classification provides a simple and natural way to tackle the problem of RNA folding prediction in presence of pseudoknots. Based on that approach, we describe a Monte Carlo algorithm for the prediction of pseudoknots in an RNA molecule.
Inverse folding of RNA pseudoknot structures
James ZM Gao, Linda YM Li, Christian M Reidys
Algorithms for Molecular Biology , 2010, DOI: 10.1186/1748-7188-5-27
Abstract: In this paper we present the inverse folding algorithm Inv. We give a detailed analysis of Inv, including pseudocodes. We show that Inv allows to design in particular 3-noncrossing nonplanar RNA pseudoknot 3-noncrossing RNA structures-a class which is difficult to construct via dynamic programming routines. Inv is freely available at http://www.combinatorics.cn/cbpc/inv.html webcite.The algorithm Inv extends inverse folding capabilities to RNA pseudoknot structures. In comparison with RNAinverse it uses new ideas, for instance by considering sets of competing structures. As a result, Inv is not only able to find novel sequences even for RNA secondary structures, it does so in the context of competing structures that potentially exhibit cross-serial interactions.Pseudoknots are structural elements of central importance in RNA structures [1], see Figure 1. They represent cross-serial base pairing interactions between RNA nucleotides that are functionally important in tRNAs, RNaseP [2], telomerase RNA [3], and ribosomal RNAs [4]. Pseudoknot structures are being observed in the mimicry of tRNA structures in plant virus RNAs as well as the binding to the HIV-1 reverse transcriptase in in vitro selection experiments [5]. Furthermore basic mechanisms, like ribosomal frame shifting, involve pseudoknots [6].Despite them playing a key role in a variety of contexts, pseudoknots are excluded from large-scale computational studies. Although the problem has attracted considerable attention in the last decade, pseudoknots are considered a somewhat "exotic" structural concept. For all we know [7], the ab initio prediction of general RNA pseudoknot structures is NP-complete and algorithmic difficulties of pseudoknot folding are confounded by the fact that the thermodynamics of pseudoknots is far from being well understood.As for the folding of RNA secondary structures, Waterman et al [8,9], Zuker et al [10] and Nussinov [11] established the dynamic programming (DP) folding routines.
Prediction of RNA Pseudoknots Using Heuristic Modeling with Mapping and Sequential Folding  [PDF]
Wayne K. Dawson, Kazuya Fujiwara, Gota Kawai
PLOS ONE , 2007, DOI: 10.1371/journal.pone.0000905
Abstract: Predicting RNA secondary structure is often the first step to determining the structure of RNA. Prediction approaches have historically avoided searching for pseudoknots because of the extreme combinatorial and time complexity of the problem. Yet neglecting pseudoknots limits the utility of such approaches. Here, an algorithm utilizing structure mapping and thermodynamics is introduced for RNA pseudoknot prediction that finds the minimum free energy and identifies information about the flexibility of the RNA. The heuristic approach takes advantage of the 5′ to 3′ folding direction of many biological RNA molecules and is consistent with the hierarchical folding hypothesis and the contact order model. Mapping methods are used to build and analyze the folded structure for pseudoknots and to add important 3D structural considerations. The program can predict some well known pseudoknot structures correctly. The results of this study suggest that many functional RNA sequences are optimized for proper folding. They also suggest directions we can proceed in the future to achieve even better results.
SimulFold: Simultaneously Inferring RNA Structures Including Pseudoknots, Alignments, and Trees Using a Bayesian MCMC Framework  [PDF]
Irmtraud M Meyer ,István Miklós
PLOS Computational Biology , 2007, DOI: 10.1371/journal.pcbi.0030149
Abstract: Computational methods for predicting evolutionarily conserved rather than thermodynamic RNA structures have recently attracted increased interest. These methods are indispensable not only for elucidating the regulatory roles of known RNA transcripts, but also for predicting RNA genes. It has been notoriously difficult to devise them to make the best use of the available data and to predict high-quality RNA structures that may also contain pseudoknots. We introduce a novel theoretical framework for co-estimating an RNA secondary structure including pseudoknots, a multiple sequence alignment, and an evolutionary tree, given several RNA input sequences. We also present an implementation of the framework in a new computer program, called SimulFold, which employs a Bayesian Markov chain Monte Carlo method to sample from the joint posterior distribution of RNA structures, alignments, and trees. We use the new framework to predict RNA structures, and comprehensively evaluate the quality of our predictions by comparing our results to those of several other programs. We also present preliminary data that show SimulFold's potential as an alignment and phylogeny prediction method. SimulFold overcomes many conceptual limitations that current RNA structure prediction methods face, introduces several new theoretical techniques, and generates high-quality predictions of conserved RNA structures that may include pseudoknots. It is thus likely to have a strong impact, both on the field of RNA structure prediction and on a wide range of data analyses.
Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations  [PDF]
A. Xayaphoummine,T. Bucher,F. Thalmann,H. Isambert
Physics , 2003, DOI: 10.1073/pnas.2536430100
Abstract: Ab initio RNA secondary structure predictions have long dismissed helices interior to loops, so-called pseudoknots, despite their structural importance. Here, we report that many pseudoknots can be predicted through long time scales RNA folding simulations, which follow the stochastic closing and opening of individual RNA helices. The numerical efficacy of these stochastic simulations relies on an O(n^2) clustering algorithm which computes time averages over a continously updated set of n reference structures. Applying this exact stochastic clustering approach, we typically obtain a 5- to 100-fold simulation speed-up for RNA sequences up to 400 bases, while the effective acceleration can be as high as 100,000-fold for short multistable molecules (<150 bases). We performed extensive folding statistics on random and natural RNA sequences, and found that pseudoknots are unevenly distributed amongst RNAstructures and account for up to 30% of base pairs in G+C rich RNA sequences (Online RNA folding kinetics server including pseudoknots : http://kinefold.u-strasbg.fr/ ).
An iterative method for prediction of RNA secondary structures in-cluding pseudoknots based on minimum of free energy and covari-ance
基于最小自由能和协变信息预测带伪结RNA二级结构 的迭代化方法

WANG Jin-Hua,LUO Zhi-Gang,GUAN Nai-Yang,YAN Fan-Mei,JIN Xin,ZHANG Wen,

遗传 , 2007,
Abstract: Most functional RNA molecules have characteristic, highly conserved structures, such as pseudoknots. But the prediction of RNA pseudoknots has largely remained a difficult problem, and many existing algorithms for prediction of RNA secondary structures do not have the ability to predict pseudoknots. Here we present a new method for predicting RNA secondary structures including pseudoknots through iteration. The algorithm combines thermodynamic and covariation information to assign scores to all possible base pairings. Base pairings are then predicted with the help of the iterated RNA folding algorithm based on minimum of free energy. Test result shows that nearly all pseudoknots are predicted. Compared to other methods, the method achieves a specificity that is among the best and a sensitivity that is nearly the best.
Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots  [PDF]
Philippe Rinaudo,Yann Ponty,Dominique Barth,Alain Denise
Computer Science , 2012,
Abstract: We present a general setting for structure-sequence comparison in a large class of RNA structures that unifies and generalizes a number of recent works on specific families on structures. Our approach is based on tree decomposition of structures and gives rises to a general parameterized algorithm, where the exponential part of the complexity depends on the family of structures. For each of the previously studied families, our algorithm has the same complexity as the specific algorithm that had been given before.
Predicting RNA Secondary Structures Including Pseudoknots by Covariance with Stacking and Minimum Free Energy

Jinwei Yang,Zhigang Luo,Xiaoyong Fang,Jinhua Wang,Kecheng Tang,

生物工程学报 , 2008,
Abstract: Prediction of RNA secondary structures including pseudoknots is a difficult topic in RNA field. Current predicting methods usually have relatively low accuracy and high complexity. Considering that the stacking of adjacent base pairs is a common feature of RNA secondary structure, here we present a method for predicting pseudoknots based on covariance with stacking and minimum free energy. A new score scheme, which combined stacked covariance with free energy, was used to assess the evaluation of base pair in our method. Based on this score scheme, we utilized an iterative procedure to compute the optimized RNA secondary structure with minimum score approximately. In each interaction, helix of high covariance and low free energy was selected until the sequences didn't form helix, so two crossing helixes which were selected from different iterations could form a pseudoknot. We test our method on data sets of ClustalW alignments and structural alignments downloaded from RNA databases. Experimental results show that our method can correctly predict the major portion of pseudoknots. Our method has both higher average sensitivity and specificity than the reference algorithms, and performs much better for structural alignments than for ClustalW alignments. Finally, we discuss the influence on the performance by the factor of covariance weight, and conclude that the best performance is achieved when lambda1 : lambda2 = 5 : 1.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.