What Makes the Arc-Preserving Subsequence Problem Hard?

Abstract : Given two arc-annotated sequences (S, P ) and (T, Q) representing RNA structures, the Arc-Preserving Subsequence (APS) problem asks whether (T, Q) can be obtained from (S, P ) by deleting some of its bases (together with their incident arcs, if any). In previous studies [3, 6], this problem has been naturally divided into subproblems reflecting intrinsic complexity of arc structures. We show that APS(Crossing, Plain) is NP-complete, thereby answering an open problem [6]. Furthermore, to get more insight into where actual border of APS hardness is, we refine APS classical subproblems in much the same way as in [11] and give a complete categorization among various restrictions of APS problem complexity.
Type de document :
Communication dans un congrès
S. Sunderam Vaidy and van Albada G. Dick and M. A. Sloot Peter and Dongarra Jack. 5th Int. Workshop on Bioinformatics Research and Applications (IWBRA'05), May 2005, Atlanta, GA, USA, United States. Springer-Verlag, 3515, pp.860-868, 2005, LNCS
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-00620359
Contributeur : Guillaume Blin <>
Soumis le : vendredi 30 septembre 2011 - 16:01:41
Dernière modification le : mercredi 23 mai 2018 - 15:44:02
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:21:16

Fichier

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

Identifiants

  • HAL Id : hal-00620359, version 1

Citation

Guillaume Blin, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette. What Makes the Arc-Preserving Subsequence Problem Hard?. S. Sunderam Vaidy and van Albada G. Dick and M. A. Sloot Peter and Dongarra Jack. 5th Int. Workshop on Bioinformatics Research and Applications (IWBRA'05), May 2005, Atlanta, GA, USA, United States. Springer-Verlag, 3515, pp.860-868, 2005, LNCS. 〈hal-00620359〉

Partager

Métriques

Consultations de la notice

510

Téléchargements de fichiers

101