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/.
