Paper Info
Title
Computing the partition function and sampling for saturated secondary structures of RNA, with respect to the Turner energy model.
Abstract
An RNA secondary structure is saturated if no base pairs can be added without violating the definition of secondary structure. Here we describe a new algorithm, RNAsat, which for a given RNA sequence a, an integral temperature 0 <= T <= 100 in degrees Celsius, and for all integers k, computes the Boltzmann partition function x(k)(T) (a) = Sigma(S is an element of SATk(a))exp(-E(S)/RT), where the sum is over all saturated secondary structures of a which have exactly k base pairs, R is universal gas constant and E(S) denotes the free energy with respect to the Turner nearest neighbor energy model. By dynamic programming, we compute Z(k)(T)simultaneously for all values of k in time O(n(5)) and space O(n(3)). Additionally, RNAsat computes the partition function Q(k)(T)(a) = Sigma S is an element of S-k(a) exp(-E(S)/RT), where the sum is over all secondary structures of a which have k base pairs; the latter computation is performed simultaneously for all values of k in O(n(4)) time and O(n(3)) space. Lastly, using the partition function Z(k)(T) [resp. Q(k)(T)]with stochastic backtracking, RNAsat rigorously samples the collection of saturated secondary structures [resp. secondary structures] having k base pairs; for Q(k)(T) this provides a parameterized form of Sfold sampling (Ding and Lawrence, 2003). Using RNAsat, (i) we compute the ensemble free energy for saturated secondary structures having k base pairs, (ii) show cooperativity of the Turner modelm (iii) demonstrate a temperature-dependent phase transition, (iv) illustrate the predictive advantage of RNAsat for the precursor microRNA cel-mire-72 of C. elegans and for the pseudoknot PKB 00152 of Pseudobase (van Batenburg et al., 2001), (v) illustrate the RNA shapes (Giegerich et al., 2004) of sampled secondary structures [resp. saturated structures]having exactly k base pairs. A web server for RNAsat is under construction of bioinformatics.bc.edu/clotelab/RNAsat/.
Year
DOI
Venue
2007
10.1089/cmb.2006.0012
JOURNAL OF COMPUTATIONAL BIOLOGY
Keywords
Field
DocType
secondary structure,RNA,Boltzmann partition function,kinetic trap
k-nearest neighbors algorithm,Integer,Discrete mathematics,Gas constant,Combinatorics,Partition function (statistical mechanics),Translational partition function,Boltzmann constant,Nucleic acid secondary structure,Mathematics,Computation
Journal
Volume
Issue
ISSN
14.0
2
1066-5277
Citations 
PageRank 
References 
7
0.54
17
Authors
2
Name
Order
Citations
PageRank
Jérôme Waldispühl111116.24
Peter Clote240047.41