title: ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs.
abstract: BACKGROUND
  Identifying sequence-structure motifs common to two RNAs can speed up the comparison of structural RNAs substantially. The core algorithm of the existent approach ExpaRNA solves this problem for a priori known input structures. However, such structures are rarely known; moreover, predicting them computationally is no rescue, since single sequence structure prediction is highly unreliable.
  
  
  RESULTS
  The novel algorithm ExpaRNA-P computes exactly matching sequence-structure motifs in entire Boltzmann-distributed structure ensembles of two RNAs; thereby we match and fold RNAs simultaneously, analogous to the well-known "simultaneous alignment and folding" of RNAs. While this implies much higher flexibility compared to ExpaRNA, ExpaRNA-P has the same very low complexity (quadratic in time and space), which is enabled by its novel structure ensemble-based sparsification. Furthermore, we devise a generalized chaining algorithm to compute compatible subsets of ExpaRNA-P's sequence-structure motifs. Resulting in the very fast RNA alignment approach ExpLoc-P, we utilize the best chain as anchor constraints for the sequence-structure alignment tool LocARNA. ExpLoc-P is benchmarked in several variants and versus state-of-the-art approaches. In particular, we formally introduce and evaluate strict and relaxed variants of the problem; the latter makes the approach sensitive to compensatory mutations. Across a benchmark set of typical non-coding RNAs, ExpLoc-P has similar accuracy to LocARNA but is four times faster (in both variants), while it achieves a speed-up over 30-fold for the longest benchmark sequences (≈400nt). Finally, different ExpLoc-P variants enable tailoring of the method to specific application scenarios. ExpaRNA-P and ExpLoc-P are distributed as part of the LocARNA package. The source code is freely available at http://www.bioinf.uni-freiburg.de/Software/ExpaRNA-P .
  
  
  CONCLUSIONS
  ExpaRNA-P's novel ensemble-based sparsification reduces its complexity to quadratic time and space. Thereby, ExpaRNA-P significantly speeds up sequence-structure alignment while maintaining the alignment quality. Different ExpaRNA-P variants support a wide range of applications.
authors.affiliation: Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. schmiedc@informatik.uni-freiburg.de.
authors.forename: Christina
authors.initials: C
authors.lastname: Otto
authors.affiliation: Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. mamo181@googlemail.com.
authors.forename: Mathias
authors.initials: M
authors.lastname: Möhl
authors.affiliation: Max Planck Institute of Immunobiology and Epigenetics, Stuebeweg 51, Freiburg, 79108, Germany. heyne@informatik.uni-freiburg.de.
authors.forename: Steffen
authors.initials: S
authors.lastname: Heyne
authors.affiliation: Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel. mika.amit2@gmail.com.
authors.forename: Mika
authors.initials: M
authors.lastname: Amit
authors.affiliation: Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel. landau@univ.haifa.ac.il.|Department of Computer Science and Engineering, NYU-Poly, Brooklyn, NY, USA. landau@univ.haifa.ac.il.
authors.forename: Gad M
authors.initials: GM
authors.lastname: Landau
authors.affiliation: Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.|Center for Biological Signaling Studies (BIOSS), University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.|Centre for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.|Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, Frederiksberg C, DK-1870, Denmark. backofen@informatik.uni-freiburg.de.
authors.forename: Rolf
authors.initials: R
authors.lastname: Backofen
authors.affiliation: Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. swill@csail.mit.edu.|Bioinformatics, Department of Computer Science, University of Leipzig, Leipzig, Germany. swill@csail.mit.edu.
authors.forename: Sebastian
authors.initials: S
authors.lastname: Will
mesh_terms: D000465:Algorithms; D012313:RNA / Q000737:chemistry; D059370:RNA Folding; D017423:Sequence Analysis, RNA; D012689:Sequence Homology, Nucleic Acid; D012984:Software
chemical_list: D012313:RNA