title: A sequence-based filtering method for ncRNA identification and its application to searching for riboswitch elements.
abstract: BACKGROUND
  Recent studies have uncovered an "RNA world", in which non coding RNA (ncRNA) sequences play a central role in the regulation of gene expression. Computational studies on ncRNA have been directed toward developing detection methods for ncRNAs. State-of-the-art methods for the problem, like covariance models, suffer from high computational cost, underscoring the need for efficient filtering approaches that can identify promising sequence segments and speedup the detection process.
  
  
  RESULTS
  In this paper we make several contributions toward this goal. First, we formalize the concept of a filter and provide figures of merit that allow comparison between filters. Second, we design efficient sequence based filters that dominate the current state-of-the-art HMM filters. Third, we provide a new formulation of the covariance model that allows speeding up RNA alignment. We demonstrate the power of our approach on both synthetic data and real bacterial genomes. We then apply our algorithm to the detection of novel riboswitch elements from the whole bacterial and archaeal genomes. Our results point to a number of novel riboswitch candidates, and include genomes that were not previously known to contain riboswitches.
  
  
  BACKGROUND
  The program is available upon request from the authors.
authors.affiliation: Department of Computer Science and Engineering, University of California San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. shzhang@cs.ucsd.edu
authors.forename: Shaojie
authors.initials: S
authors.lastname: Zhang
authors.forename: Ilya
authors.initials: I
authors.lastname: Borovok
authors.forename: Yair
authors.initials: Y
authors.lastname: Aharonowitz
authors.forename: Roded
authors.initials: R
authors.lastname: Sharan
authors.forename: Vineet
authors.initials: V
authors.lastname: Bafna
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D008969:Molecular Sequence Data; D022661:RNA, Untranslated / Q000235:genetics*; D050436:Regulatory Elements, Transcriptional / Q000235:genetics*; D012270:Ribosomes / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*
chemical_list: D022661:RNA, Untranslated