A general RNA secondary structure algorithm with vertical tree grammar

Abstract

Our understanding of the functions played by RNA molecules is expanded with the understanding of RNA structures. Except for primary structure, RNA molecules present pairings within a sequence, which is called RNA secondary structure. Since its discovery, RNA secondary structure has drawn considerable attention because it is widely appeared. Many programs for RNA secondary structure prediction have been developed, including [4, 20, 38, 39, 46]. Based on our knowledge, however, there is a family of RNA secondary structure which can not be covered by any of these algorithms. And even without considering this family, none of programs can cover all other structures in Rfam data-set. These structures are found to be important in many biological processes, for example, chromosome maintenance, RNA processing, protein biosynthesis. And efficient structure prediction can give direction for experimental investigations. Here, we present a general algorithm with a new grammar: Vertical Tree Grammar (VTG) which has stochastic context-free grammar architecture for RNA secondary structure prediction. VTG significantly expands the class of structures that can be handled, including all structures that can be covered by other paper, and all structures in Rfam data-set. Our algorithm runs in O(n^6) time, and it's precision is reasonable high, with average sensitivity and specificity over 70%.