@inproceedings{Amit-local_exact_pattern_matching-CPM2012,
  author =	 {Mika Amit and Rolf Backofen and Steffen Heyne and
                  Gad M. Landau and Mathias M{\"o}hl and Christina
                  Schmiedl and Sebastian Will},
  title =	 {Local Exact Pattern Matching for Non-fixed {RNA}
                  Structures},
  booktitle =	 {Proceedings of the 23th Annual Symposium on
                  Combinatorial Pattern Matching (CPM 2012)},
  year =	 2012,
  series =	 {LNCS},
  volume =	 7354,
  publisher =	 {Springer-Verlag},
  editors =	 {Juha K{\"a}rkk{\"a}inen and Jens Stoye},
  isbn =	 {978-3-642-31264-9},
  pages =	 {306-320},
  doi =		 {10.1007/978-3-642-31265-6_25},
  user =	 {will},
  abstract =	 {Detecting local common sequence-structure regions of
                  RNAs is a biologically meaningful problem. By
                  detecting such regions, biologists are able to
                  identify functional similarity between the inspected
                  molecules. We developed dynamic programming
                  algorithms for finding common structure-sequence
                  patterns between two RNAs. The RNAs are given by
                  their sequence and a set of potential base pairs
                  with associated probabilities. In contrast to prior
                  work which matches fixed structures, we support the
                  arc breaking edit operation; this allows to match
                  only a subset of the given base pairs. We present an
                  $O(n^3)$ algorithm for local exact pattern matching
                  between two nested RNAs, and an $O(n^3 logn)$
                  algorithm for one nested RNA and one
                  bounded-unlimited RNA.}
}