RNA plays a critical role in mediating every step of cellular information transfer from genes to functional proteins. Pseudoknots are widely occurring structural motifs found in all types of RNA and are also functionally important. Therefore predicting their structures is an important problem. In this paper, we present a new RNA pseudoknot prediction method based on term rewriting rather than on dynamic programming, comparative sequence analysis, or context-free grammars. The method we describe is implemented using the Mfold RNA/DNA folding package and the term rewriting language Maude. Our method was tested on 211 pseudoknots in PseudoBase and achieves an average accuracy of 74.085% compared to the experimentally determined structure. In fact, most pseudoknots discovered by our method achieve an accuracy of above 90%. These results indicate that term rewriting has a broad potential in RNA applications from prediction of pseudoknots to higher level RNA structures involving complex RNA tertiary interactions.

It is now well recognized that RNA structure is related to ideas from formal language theory (e.g. Context-free grammar). Primary RNA structures are simply strings of nucleotides and many researchers have applied string-based algorithms and techniques to the structure determination problems. This paper applies another idea from the study of languages — term rewriting [1] — to structure prediction.

Term rewriting is a style of computation in which an input — the term — is transformed according to a predetermined set of rules. Term rewriting has a long history in theoretical Computer Science [1] and has recently found a place in bioinformatics applications [2, 3] as well. Our method described in this paper treats RNA structures as terms and discovers rules for predicting pseudoknots.

Conventional secondary structure prediction programs like Mfold [4] do not predict pseudoknots. However, a set of common features are observed in the predictions they make for sequences that actually fold into pseudoknots. We applied term rewriting logic to recognize these consistent but inaccurate predictions and replaced them with more accurate predictions.