BIOINFORMATICS Faster computation of exact RNA shape probabilities

Motivation: Abstract shape analysis allows efcient computation of a representative sample of low-energy foldings of an RNA molecule. More comprehensive information is obtained by computing shape probabilities, accumulating the Boltzmann probabilities of all struc-tures within each abstract shape. Such information is superior to free energies because it is independent of sequence length and base composition. However, up to this point, computation of shape probabilities evaluates all shapes simultaneously and comes with a computation cost which is exponential in the length of the sequence. Results: We device an approach called RapidShapes which compu-tes the shapes above a specied probability threshold T by genera-ting a list of promising shapes and constructing specialized folding programs for each shape to compute its share of Boltzmann pro-bability. This aims at a heuristic improvement of runtime, while still computing exact probability values. Conclusion Evaluating this approach and several substrategies, we nd that only a small proportion of shapes have actually to be com-puted. For an RNA sequence of length 400 this leads, depending on the threshold, to a 10 138 fold speed-up compared to the previous complete method. Thus, probabilistic shape analysis has become feasible in medium scale applications such as the screening of RNA transcripts in a bacterial genome. Availability RapidShapes is available vi