@inproceedings{Amit-local_exact_pattern_matching-CPM2012,
author = {Amit, Mika and Backofen, Rolf and Heyne, Steffen and
          Landau, Gad M. and Möhl, Mathias and 
          Schmiedl, Christina and Will, Sebastian},
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},
doi = {10.1007/978-3-642-31265-6_25},
volume = {7354},
user = {will},
series = {LNCS},
publisher = {Springer-Verlag},
pages = {306-320},
isbn = {978-3-642-31264-9},
editors = {Juha Kärkkäinen and Jens Stoye},
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.}
}