TY - GEN
T1 - Exact pattern matching for RNA structure ensembles
AU - Schmiedl, Christina
AU - Möhl, Mathias
AU - Heyne, Steffen
AU - Amit, Mika
AU - Landau, Gad M.
AU - Will, Sebastian
AU - Backofen, Rolf
PY - 2012/5/15
Y1 - 2012/5/15
N2 - ExpaRNA's core algorithm computes, for two fixed RNA structures, a maximal non-overlapping set of maximal exact matchings. We introduce an algorithm ExpaRNA-P that solves the lifted problem of finding such sets of exact matchings in entire Boltzmann-distributed structure ensembles of two RNAs. Due to a novel kind of structural sparsification, the new algorithm maintains the time and space complexity of the algorithm for fixed input structures. Furthermore, we generalized the chaining algorithm of ExpaRNA in order to compute a compatible subset of ExpaRNA-P's exact matchings. We show that ExpaRNA-P outperforms ExpaRNA in BRAliBase 2.1 benchmarks, where we pass the chained exact matchings as anchor constraints to the RNA alignment tool LocARNA. Compared to LocARNA, this novel approach shows similar accuracy but is six times faster.
AB - ExpaRNA's core algorithm computes, for two fixed RNA structures, a maximal non-overlapping set of maximal exact matchings. We introduce an algorithm ExpaRNA-P that solves the lifted problem of finding such sets of exact matchings in entire Boltzmann-distributed structure ensembles of two RNAs. Due to a novel kind of structural sparsification, the new algorithm maintains the time and space complexity of the algorithm for fixed input structures. Furthermore, we generalized the chaining algorithm of ExpaRNA in order to compute a compatible subset of ExpaRNA-P's exact matchings. We show that ExpaRNA-P outperforms ExpaRNA in BRAliBase 2.1 benchmarks, where we pass the chained exact matchings as anchor constraints to the RNA alignment tool LocARNA. Compared to LocARNA, this novel approach shows similar accuracy but is six times faster.
UR - https://www.scopus.com/pages/publications/84860788410
U2 - 10.1007/978-3-642-29627-7_27
DO - 10.1007/978-3-642-29627-7_27
M3 - Conference contribution
AN - SCOPUS:84860788410
SN - 9783642296260
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 245
EP - 260
BT - Research in Computational Molecular Biology - 16th Annual International Conference, RECOMB 2012, Proceedings
T2 - 16th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2012
Y2 - 21 April 2012 through 24 April 2012
ER -