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, *
* Auteur correspondant
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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : 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.
Type de document :
Communication dans un congrès
Ben Raphael and Jijun Tang. WABI - 12th Workshop on Algorithms in Bioinformatics - 2012, Sep 2012, Ljubljana, Slovenia. 2012, tba
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00708580
Contributeur : Yann Ponty <>
Soumis le : dimanche 17 juin 2012 - 10:58:26
Dernière modification le : jeudi 10 mai 2018 - 02:06:53
Document(s) archivé(s) le : mardi 18 septembre 2012 - 02:22:01

Fichiers

article.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Ben Raphael and Jijun Tang. WABI - 12th Workshop on Algorithms in Bioinformatics - 2012, Sep 2012, Ljubljana, Slovenia. 2012, tba. 〈hal-00708580v2〉

Partager

Métriques

Consultations de la notice

571

Téléchargements de fichiers

307