Name
Abstract | ||
|---|---|---|
One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif M as a multiset of colors. An occurrence of a motif M in a vertex-colored graph G is a connected induced subgraph of G whose vertex set is colored exactly as M. In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when M is a set, and the graph is a tree with maximum degree 4 in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of M. Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by ∣M∣, even if the input graph has diameter 2. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2012.08.023 | Theoretical Computer Science |
Keywords | DocType | Volume |
Graph motif,Computational biology,Parameterized complexity,Algorithms,Computational complexity | Journal | 483 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Riccardo Dondi | 1 | 89 | 18.42 |
| Guillaume Fertin | 2 | 569 | 57.84 |
| Stéphane Vialette | 3 | 648 | 48.10 |