title: Genome-scale NCRNA homology search using a Hamming distance-based filtration strategy.
abstract: BACKGROUND
  NCRNAs (noncoding RNAs) play important roles in many biological processes. Existing genome-scale ncRNA search tools identify ncRNAs in local sequence alignments generated by conventional sequence comparison methods. However, some types of ncRNA lack strong sequence conservation and tend to be missed or mis-aligned by conventional sequence comparison.
  
  
  RESULTS
  In this paper, we propose an ncRNA identification framework that is complementary to existing sequence comparison tools. By integrating a filtration step based on Hamming distance and ncRNA alignment programs such as FOLDALIGN or PLAST-ncRNA, the proposed ncRNA search framework can identify ncRNAs that lack strong sequence conservation. In addition, as the ratio of transition and transversion mutation is often used as a discriminative feature for functional ncRNA identification, we incorporate this feature into the filtration step using a coding strategy. We apply Hamming distance seeds to ncRNA search in the intergenic regions of human and mouse genomes and between the Burkholderia cenocepacia J2315 genome and the Ralstonia solanacearum genome. The experimental results demonstrate that a carefully designed Hamming distance seed can achieve better sensitivity in searching for poorly conserved ncRNAs than conventional sequence comparison tools.
  
  
  CONCLUSIONS
  Hamming distance seeds provide better sensitivity as a filtration strategy for genome-wide ncRNA homology search than the existing seeding strategies used in BLAST-like tools. By combining Hamming distance seeds matching and ncRNA alignment, we are able to find ncRNAs with sequence similarities below 60%.
authors.affiliation: Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA. yannisun@msu.edu
authors.forename: Yanni
authors.initials: Y
authors.lastname: Sun
authors.forename: Osama
authors.initials: O
authors.lastname: Aljawad
authors.forename: Jikai
authors.initials: J
authors.lastname: Lei
authors.forename: Alex
authors.initials: A
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D057508:Burkholderia cenocepacia / Q000235:genetics; D017124:Conserved Sequence; D016678:Genome; D016680:Genome, Bacterial; D006801:Humans; D051379:Mice; D008969:Molecular Sequence Data; D012329:RNA, Bacterial / Q000737:chemistry / Q000235:genetics / Q000302:isolation & purification; D022661:RNA, Untranslated / Q000737:chemistry / Q000235:genetics* / Q000302:isolation & purification*; D043368:Ralstonia solanacearum / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D012329:RNA, Bacterial; D022661:RNA, Untranslated