title: RIsearch: fast RNA-RNA interaction search using a simplified nearest-neighbor energy model.
abstract: BACKGROUND
  Regulatory, non-coding RNAs often function by forming a duplex with other RNAs. It is therefore of interest to predict putative RNA-RNA duplexes in silico on a genome-wide scale. Current computational methods for predicting these interactions range from fast complementary-based searches to those that take intramolecular binding into account. Together these methods constitute a trade-off between speed and accuracy, while leaving room for improvement within the context of genome-wide screens. A fast pre-filtering of putative duplexes would therefore be desirable.
  
  
  RESULTS
  We present RIsearch, an implementation of a simplified Turner energy model for fast computation of hybridization, which significantly reduces runtime while maintaining accuracy. Its time complexity for sequences of lengths m and n is with a much smaller pre-factor than other tools. We show that this energy model is an accurate approximation of the full energy model for near-complementary RNA-RNA duplexes. RIsearch uses a Smith-Waterman-like algorithm using a dinucleotide scoring matrix which approximates the Turner nearest-neighbor energies. We show in benchmarks that we achieve a speed improvement of at least 2.4× compared with RNAplex, the currently fastest method for searching near-complementary regions. RIsearch shows a prediction accuracy similar to RNAplex on two datasets of known bacterial short RNA (sRNA)-messenger RNA (mRNA) and eukaryotic microRNA (miRNA)-mRNA interactions. Using RIsearch as a pre-filter in genome-wide screens reduces the number of binding site candidates reported by miRNA target prediction programs, such as TargetScanS and miRanda, by up to 70%. Likewise, substantial filtering was performed on bacterial RNA-RNA interaction data.
  
  
  BACKGROUND
  The source code for RIsearch is available at: http://rth.dk/resources/risearch.
authors.affiliation: Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, DK-1870 Frederiksberg, Denmark.
authors.forename: Anne
authors.initials: A
authors.lastname: Wenzel
authors.forename: Erdinç
authors.initials: E
authors.lastname: Akbasli
authors.forename: Jan
authors.initials: J
authors.lastname: Gorodkin
mesh_terms: D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D001665:Binding Sites; D016000:Cluster Analysis; D003198:Computer Simulation; D020131:Genes, Duplicate; D016247:Information Storage and Retrieval / Q000379:methods*; D035683:MicroRNAs / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D008958:Models, Molecular; D056510:Position-Specific Scoring Matrices; D012313:RNA / Q000737:chemistry / Q000235:genetics / Q000378:metabolism*; D012329:RNA, Bacterial / Q000737:chemistry; D012333:RNA, Messenger / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D022661:RNA, Untranslated / Q000235:genetics*; D016415:Sequence Alignment
chemical_list: D035683:MicroRNAs; D012329:RNA, Bacterial; D012333:RNA, Messenger; D022661:RNA, Untranslated; D012313:RNA