Rapid Annotation of Non-coding RNA Structures with a Parameterized Filtering Approach

An important problem in structural bioinformatics is to search genomes for RNA sequences with known secondary structures. Most of the existing approaches use sequence-structure alignment to evaluate the probability for a sequence segment to be a member of the searched RNA family. Due to the large amount of computation time needed by accurate sequence-structure alignments, filtering approaches have been developed to rapidly eliminate most part of the genome that are unlikely to contain sequences from the desired family. Most of the existing filtering tools construct and select filters based on the recognition ability of filters and do not consider the computation time needed by the filtering process. In this paper, we develop a parameterized filter selection approach that considers both the recognition ability and the computational efficiency of filters. As the first step, the approach constructs a set of filters that contain highly conserved parts in a searched family. A dynamic programming approach is then used to evaluate the recognition ability of each filter constructed in the first step. Finally, a set of filters are selected by solving a variant of the 0-1 knapsack problem that considers both their sizes and recognition ability. Our testing results showed that this new filtering approach can significantly speed up the search procedure without adversely affecting the search accuracy. It therefore can be combined with most of the existing search tools to significantly reduce the computation time needed for search.