@article{amit14:_local_exact_patter_match_non_fixed_struc,
   author              = {Mika Amit and 
                          Rolf Backofen and 
                          Steffen Heyne and 
                          Gad M. Landau and 
                          Mathias M{\"o}hl and 
                          Christina Otto and 
                          Sebastian Will},
   title               = {Local Exact Pattern Matching for Non-Fixed {RNA} Structures.},
   journal             = {IEEE/ACM Trans. Comput. Biology Bioinform.},
   year                = 2014,
   volume 		 = {11},
   number 		 = {1},
   pages               = {219-230},
   doi 			 = {10.1109/TCBB.2013.2297113},
   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.},
  user =	 {backofen}
}