TREE ADJOINING GRAMMARS FOR RNA STRUCTURE PREDICTION

In this paper, we are concerned with identifying a subclass of tree ad joining grammars (TAGs) that is suitable for the application to modeli ng and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure pr ediction problem, we first introduce a special subclass of TAGs and de velop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorith m, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biol ogical data, where free energy evaluation selection for parse trees is incorporated into the algorithm. (C) 1999-Elsevier Science B.V. All r ights reserved.