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.
Complete list of metadatas

https://hal.inria.fr/hal-00708580
Contributor : Yann Ponty <>
Submitted on : Friday, June 15, 2012 - 1:08:37 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Sunday, September 16, 2012 - 2:50:08 AM

Files

article.pdf
Files produced by the author(s)

Identifiers

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

Citation

Philippe Rinaudo, Yann Ponty, Dominique Barth, Alain Denise. Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. 2012. ⟨hal-00708580v1⟩

Share

Metrics

Record views

25

Files downloads

132