Algorithms for pseudoknot classification

The structures of non-coding RNAs are found to be critical in many biological functions. In particular, pseudoknotted structures play an important role in some of these functions. Different pseudoknotted structures may have different functionalities. Algorithms developed to handle pseudoknotted ncRNAs are usually designed for specific pseudoknot structures (e.g. structural alignment algorithms). It is desirable to have a tool to classify a given RNA secondary structure into different types. In this paper, we solve this problem by providing a set of efficient algorithms to perform the classification. We implemented the algorithms and used them in the web-based tool RNASAlign (http://www.bio8.cs.hku.hk/RNASAlign) which can automatically classify the input structure into the correct type, then perform the structural alignment according to the identified type. The classification algorithms proposed in the paper are found to be effective.