Teaching RNA algorithms
Using an adapted umambigous version of the Nussinov algorithm it is possible to count the number of all possible nested secondary structures an RNA molecule can form.
The Nussinov algorithm enables the efficient computation of the structure with the maximal number of base pairs for a given RNA sequence.
The McCaskill algorithm enables the efficient computation of RNA structure probabilities as well as probabilities that a certain base pair is formed. Furthermore, unpaired probabilities for subsequences can be computed that reflect the accessibility of RNA parts for other interactions.
The maximum expected accuracy (MEA) algorithm uses base pair probabilities as well as unpaired probabilites (e.g. computed via the McCaskill algorithm) to find the structure that is 'maximally accurate' in its structural elements.
RNA-RNA interactions can be predicted by linking the two interacting RNAs into one pseudo-RNA and use a variant of the Nussinov algorithm to predict the fused structure. Such approaches are called 'co-folding'.
Given two RNA molecules, the RNA-RNA interaction with the maximal number of intermolecular base pairs can be predicted. Such algorithms ignore the competition between intra- and intermolecular base pair formation, e.g. considered in 'co-folding' or 'accessibilty-based' approaches.
Since a nucleotide can form at most one base pair, there is a competition between intra- and intermolecular base pair formation. This can be incorporated into RNA-RNA interaction prediction by also scoring the probability that an interacting subsequence is not involved in intramolecular base pairs, i.e. it is accessible.