TY - GEN
T1 - Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots
AU - Möhl, Mathias
AU - Will, Sebastian
AU - Backofen, Rolf
PY - 2008/7/1
Y1 - 2008/7/1
N2 - We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.
AB - We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.
KW - Fixed parameter tractability
KW - Pseudoknots
KW - RNA alignment
UR - https://www.scopus.com/pages/publications/45849125023
U2 - 10.1007/978-3-540-69068-9_9
DO - 10.1007/978-3-540-69068-9_9
M3 - Conference contribution
AN - SCOPUS:45849125023
SN - 3540690662
SN - 9783540690665
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 69
EP - 81
BT - Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
T2 - 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Y2 - 18 June 2008 through 20 June 2008
ER -