10 - RNA structure analysis

Summary

Stochastic transformational grammars, particularly stochastic context-free grammars, turned out to be effective modeling tools for RNA sequence analysis. Two biologically interesting problems are the prediction of RNA secondary structure and the construction of multiple alignments of RNA families. Non-stochastic algorithms for the RNA secondary structure prediction were developed more than twenty years ago (by Nussinov et al. (1978) and by Zuker and Stiegler (1981)). Notably, the Nussinov algorithm could be immediately rewritten in SCFG terms as a version of the Cocke–Younger–Kasami (CYK) algorithm. The SCFG interpretation provides an insight into the probabilistic meaning of parameters of the original Nussinov algorithm and also suggests statistical procedures for parameter estimation. A similar translation into SCFG terms is possible for the Zuker algorithm.

Interestingly, equivalence between the non-probabilistic dynamic programming sequence alignment algorithm and the Viterbi algorithm for a pair HMM is analogous to equivalence between the non-probabilistic algorithm of RNA structure prediction and the CYK algorithm for a SCFG. There is also an analogy between the use of the profile HMM for alignment of multiple DNA or protein sequences and the use of the SCFG-based RNA structure profiles, called covariance models (CMs), for constructing structurally sound alignments of multiple RNAs. Furthermore, parameters of the covariance models could be derived by the inside–outside expectation maximization algorithm (compare with the simultaneous profile HMM parameter estimation and construction of multiple sequence alignment).