Fast and accurate search for non-coding RNA pseudoknot structures in genomes

• DOI: 10.1093/bioinformatics/btn393
• Publication Date: 2008-08-08T00:14:16Z
• Authors: Zhibin Huang; Yong Wu; Joseph Robertson; Liang Feng; Russell L. Malmberg; Liming Cai
• Keywords: Pseudoknot; Heuristics; Nucleic acid structure

Abstract Motivation: Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, computational difficulty in aligning RNA sequence to a pseudoknot prohibited fast accurate of arbitrary structures. Our previous work introduced graph pseudoknots proposed solve structure–sequence alignment optimization. Given k candidate regions target each n stems structure, we could compute best time O(ktn) upon tree width t decomposition graph. implement this method programs that routinely perform yet searches, need novel heuristics ensure that, without degrading accuracy, only small number stem candidates examined always found Results: The current builds one with newly developed preprocessing algorithms reduce values parameters into practical program, called RNATOPS, search. In particular, introduce techniques, probabilistic profiling distance penalty functions, which identify every just (e.g. ≤ 10) plausible needs align. We also devised specialized algorithm yield 4) almost all graphs. experiments show RNATOPS it is possible prokaryotic eukaryotic specific structures medium large sizes, including pseudoknots, high sensitivity specificity, reasonable amount time. Availability: source code C++ available at www.uga.edu/RNA-Informatics/software/rnatops/ Contact: [e-mail] Supplementary information: online Material contains illustrative figures tables referenced article.