An RNA secondary structure is saturated if no base pairs can be added without violating the definition of secondary structure. Herewe 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 , 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 simultaneously for all values of k in time O(n (5)) and space O(n (3)).Additionally, RNAsat computes the partition function , 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 [resp. ] with stochastic backtracking, RNAsat rigorously samples the collection of saturated secondary structures [resp. secondary structures] having k base pairs; for 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/.