• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Some Results on More Flexible Versions of Graph Motif

Thumbnail
Date
2015
Link to item file
https://arxiv.org/abs/1202.5184v2
Dewey
Méthodes informatiques spéciales
Sujet
Computational biology; Graph motif problem; Biological networks; Computational complexity
Journal issue
Theory of Computing Systems
Volume
56
Number
4
Publication date
2015
Article pages
612-629
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00224-014-9564-6
URI
https://basepub.dauphine.fr/handle/123456789/14070
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Rizzi, Romeo
50732 Dipartimento di Matematica e Informatica - Universita Udine [DIMI]
Sikora, Florian
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif: one where the size of the solution is maximized, the other when the number of substitutions of colors to obtain the motif from the solution is minimized. We also study a decision version of Graph Motif where the connectivity constraint is replaced by the well known notion of graph modularity. While the problem remains N P-complete, it allows algorithms in F P T for biologically relevant parameterizations.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.