|
|
Résultat majeur : TREE DECOMPOSITION AND PARAMETERIZED ALGORITHMS FOR RNA STRUCTURE-SEQUENCE ALIGNMENT INCLUDING TERTIARY INTERACTIONS AND PSEUDOKNOTS |
 |
|
 |
|
TREE DECOMPOSITION AND PARAMETERIZED ALGORITHMS FOR RNA STRUCTURE-SEQUENCE ALIGNMENT INCLUDING TERTIARY INTERACTIONS AND PSEUDOKNOTS
07 août 2012
Philippe Rinaudo, Yann Ponty, Dominique Barth, and Alain Denise. WABI 2012.
|
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 {em 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.
Activités de recherche
° Algorithmique ° Bioinformatique
Equipe
° Bioinformatique
Contact
° DENISE Alain
|
| |
|
|
|
|
