@article{amit14:_local_exact_patter_match_non_fixed_struc,
author = {Amit, Mika and 
          Backofen, Rolf and 
          Heyne, Steffen and 
          Landau, Gad M. and 
          Möhl, Mathias and 
          Otto, Christina and 
          Will, Sebastian},
title = {Local Exact Pattern Matching for Non-Fixed {RNA} Structures.},
journal = {IEEE/ACM Trans. Comput. Biology Bioinform.},
year = {2014},
doi = {10.1109/TCBB.2013.2297113},
volume = {11},
user = {backofen},
pages = {219-230},
number = {1},
issn = {1545-5963},
abstract = {Detecting local common sequence-structure
            regions of RNAs is a biologically important
            problem. Detecting such regions allows biologists to
            identify functionally relevant similarities 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 on local pattern matching of RNAs, we
            support the breaking of arcs. This allows us to add
            flexibility over matching only fixed structures;
            potentially matching only a similar subset of
            specified base pairs. We present an $O(n^3)$ algorithm
            for local exact pattern matching between two nested
            RNAs, and an $O(n^3 log n)$ algorithm for one nested
            RNA and one bounded-unlimited RNA. In addition, an
            algorithm for approximate pattern matching is
            introduced that for two given nested RNAs and a number
            $k$, finds the maximal local pattern matching score
            between the two RNAs with at most $k$ mismatches in
            $O(n^3k^2)$ time. Finally, we present an $O(n^3)$
            algorithm for finding the most similar subforest
            between two nested RNAs.}
}