title: Fast filtering for RNA homology search.
abstract: BACKGROUND
  Homology search for RNAs can use secondary structure information to increase power by modeling base pairs, as in covariance models, but the resulting computational costs are high. Typical acceleration strategies rely on at least one filtering stage using sequence-only search.
  
  
  RESULTS
  Here we present the multi-segment CYK (MSCYK) filter, which implements a heuristic of ungapped structural alignment for RNA homology search. Compared to gapped alignment, this approximation has lower computation time requirements (O(N⁴) reduced to O(N³), and space requirements (O(N³) reduced to O(N²). A vector-parallel implementation of this method gives up to 100-fold speed-up; vector-parallel implementations of standard gapped alignment at two levels of precision give 3- and 6-fold speed-ups. These approaches are combined to create a filtering pipeline that scores RNA secondary structure at all stages, with results that are synergistic with existing methods.
authors.affiliation: Janelia Farm Research Campus, Howard Hughes Medical Institute, Ashburn, VA 20147, USA.
authors.forename: Diana L
authors.initials: DL
authors.lastname: Kolbe
authors.forename: Sean R
authors.initials: SR
authors.lastname: Eddy
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D016384:Consensus Sequence; D006801:Humans; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D016415:Sequence Alignment; D017423:Sequence Analysis, RNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software
chemical_list: D012313:RNA