TY - GEN
T1 - Local exact pattern matching for non-fixed RNA structures
AU - Amit, Mika
AU - Backofen, Rolf
AU - Heyne, Steffen
AU - Landau, Gad M.
AU - Möhl, Mathias
AU - Schmiedl, Christina
AU - Will, Sebastian
PY - 2012/7/4
Y1 - 2012/7/4
N2 - 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 3logn) algorithm for one nested RNA and one bounded-unlimited RNA.
AB - 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 3logn) algorithm for one nested RNA and one bounded-unlimited RNA.
UR - https://www.scopus.com/pages/publications/84863104682
U2 - 10.1007/978-3-642-31265-6_25
DO - 10.1007/978-3-642-31265-6_25
M3 - Conference contribution
AN - SCOPUS:84863104682
SN - 9783642312649
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 306
EP - 320
BT - Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings
T2 - 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012
Y2 - 3 July 2012 through 5 July 2012
ER -