06065612

a

06065612 Amit, Mika Backofen, Rolf Heyne, Steffen Landau, Gad M. M\"ohl, Mathias Schmiedl, Christina Will, Sebastian Local exact pattern matching for non-fixed RNA structures. K\"arkk\"ainen, Juha (ed.) et al., Combinatorial pattern matching. 23rd annual symposium, CPM 2012, Helsinki, Finland, July 3--5, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31264-9/pbk). Lecture Notes in Computer Science 7354, 306-320 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-31265-6_25

Summary: 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} \log n)$ algorithm for one nested RNA and one bounded-unlimited RNA.