Predictions using hidden Markov models and stochastic context-free grammars
Abstract
In systems where certain qualities are not directly observable, hidden Markov models provide a way to represent both the observable and hidden data. For systems behaving as Markov chains, the observable data can be analyzed to make predictions about the underlying system. The prediction process utilizes HMMs and a dynamic programming method called the Viterbi algorithm. The predictions are also run against simulation data to determine the accuracy of the algorithm. The accuracy measurements used here are positive predictive value and sensitivity, both of which tell about the likelihood of a prediction being correct. Similarly, for RNA strands, their three-dimensional structure is modelled using a two-dimensional approximation called a secondary structure. This secondary structure is predicted by used stochastic context-free grammars, a generalization of HMMs. The contextfree grammars act in place of Markov chains, and the CYK algorithm acts analogously to the Viterbi algorithm in making predictions using SCFGs.