Show simple item record

dc.contributor.authorRizzi, Romeo*
dc.contributor.authorSikora, Florian*
dc.date.accessioned2014-10-30T12:44:01Z
dc.date.available2014-10-30T12:44:01Z
dc.date.issued2015
dc.identifier.issn1432-4350
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14070
dc.language.isoenen
dc.subjectComputational biology
dc.subjectGraph motif problem
dc.subjectBiological networks
dc.subjectComputational complexity
dc.subject.ddc006en
dc.titleSome Results on More Flexible Versions of Graph Motif
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.
dc.relation.isversionofjnlnameTheory of Computing Systems
dc.relation.isversionofjnlvol56
dc.relation.isversionofjnlissue4
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages612-629
dc.relation.isversionofdoi10.1007/s00224-014-9564-6
dc.identifier.urlsitehttps://arxiv.org/abs/1202.5184v2
dc.relation.isversionofjnlpublisherSpringer
dc.subject.ddclabelMéthodes informatiques spécialesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintouien
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-06-01T14:55:05Z
hal.person.labIds50732*
hal.person.labIds989*
hal.identifierhal-01505510*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record