Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

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

Résumé

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.
Nous présentons un cadre général pour la comparaison structure/séquence d'une très large classe de structures d'ARN, qui généralise de nombreux travaux récents consacrés à des familles spécifiques. Notre approche, basée sur une décomposition arborescente des structures, permet d'obtenir un algorithme de complexité paramétrée, dont la complexité asymptotique, exponentielle dans le cas général, dépend de la famille de structures considérée. Pour chacune des familles considérées par les travaux antérieurs, notre algorithme se spécialise automatiquement, et permet d'obtenir une complexité égale à celle obtenue jusqu'alors.
Fichier principal
Vignette du fichier
article.pdf (268.81 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00708580 , version 1 (15-06-2012)
hal-00708580 , version 2 (17-06-2012)

Identifiants

Citer

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⟩
312 Consultations
382 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More