A runtime heuristic for faster probabilistic analysis of RNA abstract shapes

Biologists often deduce function of a molecule by analysing its structure. Observing RNA structures is nearly impossible, which raises the need for computational predictions. In this research paper we present a runtime heuristic for the probabilistic shape analysis which predicts functional classes of secondary structures for RNA sequences. Due to the methodology of algebraic dynamic programming we are able to precisely separate the search space and dynamically compile so called Thermodynamic Matchers which compute the probability of exactly one shape class. By a clever choice for shape classes for this procedure we achieve a runtime speed up ranging from three fold for smaller sequences up to 300 fold for sequences with more than 400 nucleotides. This advantage must be bought by an uncertainty about a small part of the complete search space that is not explored any more