Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots

Philippe Rinaudo 1, 2, 3 Yann Ponty 2, 4 Dominique Barth 3 Alain Denise 1, 2, 5, *
* Corresponding author
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : 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 on structures. Our approach is based on tree decomposition of structures and gives rises to a general parameterized algorithm, where the exponential part of the complexity depends on the family of structures. For each of the previously studied families, our algorithm has the same complexity as the specific algorithm that had been given before.
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00708580
Contributor : Yann Ponty <>
Submitted on : Sunday, June 17, 2012 - 10:58:26 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Document(s) archivé(s) le : Tuesday, September 18, 2012 - 2:22:01 AM

Files

article.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00708580, version 2
  • ARXIV : 1206.3789

Collections

Citation

Philippe Rinaudo, Yann Ponty, Dominique Barth, Alain Denise. Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. WABI - 12th Workshop on Algorithms in Bioinformatics - 2012, University of Ljubljana, Sep 2012, Ljubljana, Slovenia. ⟨hal-00708580v2⟩

Share

Metrics

Record views

600

Files downloads

397