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 <or= T <or= 100 in degrees Celsius, and for all integers k, computes the Boltzmann partition function Z(k)(T)(a) = SigmaSepsilonSAT(k)(a) exp(-E(S)/RT), where the sum is over all saturated secondary structures of a which have exactly k base pairs, R is the 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) = SigmaSepsilonS(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 parametrized 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 model, (iii) demonstrate a temperature-dependent phase transition, (iv) illustrate the predictive advantage of RNAsat for precursor microRNA cel-mir-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 at bioinformatics.bc.edu/clotelab/RNAsat/.
authors: Department of Biology, Boston College, Chestnut Hill, Massachusetts, USA.
authors: J
authors: J
authors: Waldispühl
authors: P
authors: P
authors: Clote
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D035683:MicroRNAs / Q000737:chemistry / Q000235:genetics; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D012322:RNA Precursors / Q000737:chemistry / Q000235:genetics; D013816:Thermodynamics
chemical_list: D035683:MicroRNAs; D012322:RNA Precursors; D012313:RNA