Bioinformatics 20(Suppl. 1) © Oxford University Press 2004; all rights reserved.
Exploiting conserved structure for faster annotation of non-coding RNAs without loss of accuracy
1 Department of Computer Science and Engineering and 2 Department of Genome Sciences, University of Washington, Seattle, WA 98195, USA
Received on January 15, 2004; accepted on March 1, 2004
Motivation: Non-coding RNAs (ncRNAs)—functional RNA molecules not coding for proteins—are grouped into hundreds of families of homologs. To find new members of an ncRNA gene family in a large genome database, covariance models (CMs) are a useful statistical tool, as they use both sequence and RNA secondary structure information. Unfortunately, CM searches are slow. Previously, we introduced ‘rigorous filters’, which provably sacrifice none of CMs' accuracy, although often scanning much faster. A rigorous filter, using a profile hidden Markov model (HMM), is built based on the CM, and filters the genome database, eliminating sequences that provably could not be annotated as homologs. The CM is run only on the remainder. Some biologically important ncRNA families could not be scanned efficiently with this technique, largely due to the significance of conserved secondary structure relative to primary sequence in identifying these families. Current heuristic filters are also expected to perform poorly on such families.
Results: By augmenting profile HMMs with limited secondary structure information, we obtain rigorous filters that accelerate CM searches for virtually all known ncRNA families from the Rfam Database and tRNA models in tRNAscan-SE. These filters scan an 8 gigabase database in weeks instead of years, and uncover homologs missed by heuristic techniques to speed CM searches.
Availability: Software in development; contact the authors.
Supplementary information: http://bio.cs.washington.edu/supplements/zasha-ISMB-2004 (Additional technical details on the method; predicted homologs.)
Contact: zasha{at}cs.washington.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  Z. Weinberg, J. E. Barrick, Z. Yao, A. Roth, J. N. Kim, J. Gore, J. X. Wang, E. R. Lee, K. F. Block, N. Sudarsan, et al. Identification of 22 candidate structured RNAs in bacteria using the CMfinder comparative genomics pipeline Nucleic Acids Res., July 9, 2007; (2007) gkm487v1. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. St-Onge, P. Thibault, S. Hamel, and F. Major Modeling RNA tertiary structure motifs by graph-grammars Nucleic Acids Res., March 27, 2007; (2007) gkm069v2. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. Torarinsson, M. Sawera, J. H. Havgaard, M. Fredholm, and J. Gorodkin Thousands of corresponding human and mouse genomic regions unalignable in primary sequence contain common RNA structure Genome Res., July 1, 2006; 16(7): 885 - 889. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Z. Weinberg and W. L. Ruzzo Sequence-based heuristics for faster annotation of non-coding RNA families Bioinformatics, January 1, 2006; 22(1): 35 - 39. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. E. BARRICK, N. SUDARSAN, Z. WEINBERG, W. L. RUZZO, and R. R. BREAKER 6S RNA is a widespread regulator of eubacterial RNA polymerase that resembles an open promoter RNA, May 1, 2005; 11(5): 774 - 784. [Abstract] [Full Text] [PDF]
|
|