Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

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

(1, 2, 3) , (2, 4) , (3) , (1, 2, 5)
1
2
3
4
5

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.
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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
302 View
357 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More