@InProceedings{Schmiedl:etal:_exparnap:RECOMB2012,
  author =	 {Christina Schmiedl and Mathias M{\"o}hl and Steffen
                  Heyne and Mika Amit and Gad M. Landau and Sebastian
                  Will and Rolf Backofen},
  title =	 {Exact Pattern Matching for {RNA} Structure
                  Ensembles},
  booktitle =	 {Proceedings of the 16th International Conference on
                  Research in Computational Molecular Biology (RECOMB
                  2012)},
  pages =	 {245-260},
  year =	 2012,
  series =	 {LNCS},
  volume =	 7262,
  isbn =	 {978-3-642-29626-0},
  editors =	 {Benny Chor},
  publisher =	 {Springer-Verlag},
  user =	 {will},
  doi =		 {10.1007/978-3-642-29627-7_27},
  abstract =	 {ExpaRNA's core algorithm computes, for two fixed RNA
                  structures, a maximal non-overlapping set of maximal
                  exact matchings. We introduce an algorithm ExpaRNA-P
                  that solves the lifted problem of finding such sets
                  of exact matchings in entire Boltzmann-distributed
                  structure ensembles of two RNAs. Due to a novel kind
                  of structural sparsification, the new algorithm
                  maintains the time and space complexity of the
                  algorithm for fixed input structures. Furthermore,
                  we generalized the chaining algorithm of ExpaRNA in
                  order to compute a compatible subset of ExpaRNA-P's
                  exact matchings.We show that ExpaRNA-P outperforms
                  ExpaRNA in BRAliBase 2.1 benchmarks, where we pass
                  the chained exact matchings as anchor constraints to
                  the RNA alignment tool LocARNA.  Compared to
                  LocARNA, this novel approach shows similar accuracy
                  but is six times faster.}
}