TY - GEN
T1 - Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots (extended abstract)
AU - Rinaudo, Philippe
AU - Ponty, Yann
AU - Barth, Dominique
AU - Denise, Alain
PY - 2012/10/1
Y1 - 2012/10/1
N2 - We present a general setting for structure-sequence comparison in a large class of RNA structures, that unifies and generalizes a number of recent works on specific families of structures. Our approach is based on a tree decomposition of structures, and gives rise to a general parameterized algorithm having complexity in O(N·m t), where N (resp. m) is the structure (resp. sequence) length, and the exponent t depends on the family of structures. For each family considered by previous approaches, our contribution specializes into an algorithm whose complexity either matches or outperforms previous solutions.
AB - We present a general setting for structure-sequence comparison in a large class of RNA structures, that unifies and generalizes a number of recent works on specific families of structures. Our approach is based on a tree decomposition of structures, and gives rise to a general parameterized algorithm having complexity in O(N·m t), where N (resp. m) is the structure (resp. sequence) length, and the exponent t depends on the family of structures. For each family considered by previous approaches, our contribution specializes into an algorithm whose complexity either matches or outperforms previous solutions.
U2 - 10.1007/978-3-642-33122-0_12
DO - 10.1007/978-3-642-33122-0_12
M3 - Conference contribution
AN - SCOPUS:84866654023
SN - 9783642331213
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 149
EP - 164
BT - Algorithms in Bioinformatics - 12th International Workshop, WABI 2012, Proceedings
T2 - 12th International Workshop on Algorithms in Bioinformatics, WABI 2012
Y2 - 10 September 2012 through 12 September 2012
ER -