Modeling the secondary and pseudo-knot structures in RNA sequences is an important problem in computational biology. Stochastic Context Free Grammars (SCFG) provide a viable description of the secondary structures with nested and parallel helices. Based upon the SCFG, structure prediction can be performed with a dynamic programming algorithm. To precisely model the crossing patterns of double helices in a pseudo-knot structure, Cai et al. used the Parallel Communicating Grammar System (PCGS) and developed a dynamic programming that can predict the optimal structure for an RNA sequence containing pseudo-knots. Unfortunately, the algorithm requires a space consumption of O(N 4 ), which prevents its application to the prediction of long sequences.
The main contribution of this thesis is the development of a new scheme. The scheme can be combined with the simulated annealing algorithm to predict RNA sequences containing pseudo-knots. Compared with the dynamic programming algorithm, this approach requires less computational resources and its resource requirements increase linearly when the pseudo-knot becomes structurally more complex.