Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints

Guillaume Blin 1 Guillaume Fertin 1 Danny Hermelin 2 Stéphane Vialette 3
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 Department of Computer Science [Haifa]
3 LRI - Laboratoire de Recherche en Informatique
Abstract : In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally satisfies some secondary structure constraints, the so-called MRSO problem introduced in [3]. Since the MRSO problem is known to be APX-hard [8], Bongartz proposed in [8] to attack the problem using the concept of parameterized complexity. We prove in this paper that the MRSO problem is fixed-parameter tractable parameterized by the number of degree 3 vertices or by the number of crossing edges in the implied structure graph. This latter result answers an open problem posed in [8]. Aiming at precisely defining the complexity landscape of the problem, we refine the NP-hardness result of [3] and complement this result by showing that the MRSO problem is fixed-parameter tractable parameterized by an additional parameter. Finally, we present a fixed parameter algorithm parameterized by the similarity score in a restrictive model.
Type de document :
Communication dans un congrès
Kratsch Dieter. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), Jun 2005, Metz, France, France. Springer-Verlag, 3787, pp.271-282, 2005, LNCS
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
https://hal-upec-upem.archives-ouvertes.fr/hal-00620363
Contributeur : Guillaume Blin <>
Soumis le : vendredi 30 septembre 2011 - 16:00:09
Dernière modification le : mercredi 23 mai 2018 - 15:44:02
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:21:29

Fichier

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

Identifiants

  • HAL Id : hal-00620363, version 1

Collections

LINA | UNIV-NANTES | UNIV-MLV | LIGM | LIGM_ALGO | ENPC | PARISTECH | UPEC-UPEM | UMR8623 | LINA-COMBI | INRIA

Citation

Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette. Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints. Kratsch Dieter. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), Jun 2005, Metz, France, France. Springer-Verlag, 3787, pp.271-282, 2005, LNCS. 〈hal-00620363〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

636

Téléchargements de fichiers

84

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD