Faster computation of exact RNA shape probabilities.
BACKGROUND
Abstract shape analysis allows efficient 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 structures 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 that computes the shapes above a specified probability threshold T by generating a list of promising shapes and constructing specialized folding programs for each shape to compute its share of Boltzmann probability. This aims at a heuristic improvement of runtime, while still computing exact probability values.


CONCLUSIONS
Evaluating this approach and several substrategies, we find that only a small proportion of shapes have to be actually computed. For an RNA sequence of length 400, this leads, depending on the threshold, to a 10-138 fold speed-up compared with 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.


BACKGROUND
RapidShapes is available via http://bibiserv.cebitec.uni-bielefeld.de/rnashapes
Janssen
Stefan
S
Practical Computer Science, Faculty of Technology, Bielefeld University, D-33615 Bielefeld, Germany.
Giegerich
Robert
R
D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA
D012313:RNA