Bioinformatics Advance Access originally published online on August 7, 2008
Bioinformatics 2008 24(20):2281-2287; doi:10.1093/bioinformatics/btn393
Fast and accurate search for non-coding RNA pseudoknot structures in genomes
1Department of Computer Science, 2Institute of Bioinformatics and 3Department of Plant Biology University of Georgia, Athens, GA 30602
*To whom correspondence should be addressed.
 |
Abstract |
|---|
Motivation: Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal for bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, the computational difficulty in aligning an RNA sequence to a pseudoknot has prohibited fast and accurate search of arbitrary RNA structures. Our previous work introduced a graph model for RNA pseudoknots and proposed to solve the structure–sequence alignment by graph optimization. Given k candidate regions in the target sequence for each of the n stems in the structure, we could compute a best alignment in time O(ktn) based upon a tree width t decomposition of the structure graph. However, to implement this method to programs that can routinely perform fast yet accurate RNA pseudoknot searches, we need novel heuristics to ensure that, without degrading the accuracy, only a small number of stem candidates need to be examined and a tree decomposition of a small tree width can always be found for the structure graph.
Results: The current work builds on the previous one with newly developed preprocessing algorithms to reduce the values for parameters k and t and to implement the search method into a practical program, called RNATOPS, for RNA pseudoknot search. In particular, we introduce techniques, based on probabilistic profiling and distance penalty functions, which can identify for every stem just a small number k (e.g. k 
10) of plausible regions in the target sequence to which the stem needs to align. We also devised a specialized tree decomposition algorithm that can yield tree decomposition of small tree width t (e.g. t 4) for almost all RNA structure graphs. Our experiments show that with RNATOPS it is possible to routinely search prokaryotic and eukaryotic genomes for specific RNA structures of medium to large sizes, including pseudoknots, with high sensitivity and high specificity, and in a reasonable amount of time.
Availability: The source code in C++ for RNATOPS is available at www.uga.edu/RNA-Informatics/software/rnatops/
Contact: cai{at}cs.uga.edu
Supplementary information: The online Supplementary Material contains all illustrative figures and tables referenced by this article.
The authors wish it to be known that, in their opinion, the first two authors should be regarded as joint First Authors.
Associate Editor: Ivo Hofacker
Received on April 23, 2008; revised on June 20, 2008; accepted on July 25, 2008
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  E. P. Nawrocki, D. L. Kolbe, and S. R. Eddy Infernal 1.0: inference of RNA alignments Bioinformatics, May 15, 2009; 25(10): 1335 - 1337. [Abstract] [Full Text] [PDF]
|
|