Abstract
One of the emerging topics in the analysis of biological networks is the inference of motifs inside a network. In the context of metabolic network analysis, a recent approach introduced in [14], represents the network as a vertex-colored graph, while a motif \(\mathcal{M}\) is represented as a multiset of colors. An occurrence of a motif \(\mathcal{M}\) in a vertex-colored graph G is a connected induced subgraph of G whose vertex set is colored exactly as \(\mathcal{M}\). We investigate three different variants of the initial problem. The first two variants, Min-Add and Min-Substitute, deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (or CGM for short), constrains the motif to contain a given set of vertices. We investigate the classical and parameterized complexity of the three problems. We show that Min-Add and Min-Substitute are NP-hard, even when \(\mathcal{M}\) is a set, and the graph is a tree of degree bounded by 4 in which each color appears at most twice. Moreover, we show that Min-Substitute is in FPT when parameterized by the size of \(\mathcal{M}\). Finally, we consider the parameterized complexity of the CGM problem, and we give a fixed-parameter algorithm for graphs of bounded treewidth, while we show that the problem is W[2]-hard, even if the input graph has diameter 2.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the Kernelization Complexity of Colorful Motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010)
Alimonti, P., Kann, V.: Some APX-Completeness Results for Cubic Graphs. Theor. Comput. Sci. 237(1-2), 123–134 (2000)
Alon, N., Yuster, R., Zwick, U.: Color Coding. Journal of the ACM 42(4), 844–856 (1995)
Betzler, N., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized Algorithms and Hardness Results for Some Graph Motif Problems. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 31–43. Springer, Heidelberg (2008)
Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-Free Querying of Protein Interaction Networks. In: Batzoglou, S. (ed.) RECOMB 2009. LNCS, vol. 5541, pp. 74–89. Springer, Heidelberg (2009)
Cesati, M.: Compendium of parameterized problems, http://bravo.ce.uniroma2.it/home/cesati/research/compendium.pdf
Dondi, R., Fertin, G., Vialette, S.: Weak Pattern Matching in Colored Graphs: Minimizing the Number of Connected Components. In: Italiano, G.F., Moggi, E., Laura, L. (eds.) ICTCS 2007, pp. 27–38. World Scientific, Singapore (2007)
Dondi, R., Fertin, G., Vialette, S.: Maximum Motif Problem in Vertex-Colored Graphs. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol. 5577, pp. 221–235. Springer, Heidelberg (2009)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)
Fellows, M., Fertin, G., Hermelin, D., Vialette, S.: Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340–351. Springer, Heidelberg (2007)
Guillemot, S., Sikora, F.: Finding and Counting Vertex-Colored Subtrees. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 405–416. Springer, Heidelberg (2010)
Kelley, B.P., Sharan, R., Karp, R.M., Sittler, T., Root, D.E., Stockwell, B.R., Ideker, T.: Conserved Pathways within Bacteria and Yeast as Revealed by Global Protein Network Alignment. Proc. Nat. Acad. Sci. 100(20), 11394–11399 (2003)
Koyutürk, M., Grama, A., Szpankowski, W.: Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3500, pp. 48–65. Springer, Heidelberg (2005)
Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif Search in Graphs: Application to Metabolic Networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 3(4), 360–368 (2006)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Paz, A., Moran, S.: Non Deterministic Polynomial Optimization Problems and Their Approximations. Theor. Comput. Sci. 15, 251–277 (1981)
Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. Journal of Computational Biology 13, 133–144 (2006)
Sharan, R., Ideker, T., Kelley, B., Shamir, R., Karp, R.M.: Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data. In: Bourne, P.E., Gusfield, D. (eds.) RECOMB 2004, pp. 282–289. ACM Press, New York (2004)
Sharan, R., Suthram, S., Kelley, R., Kuhn, T., McCuine, S., Uetz, P., Sittler, K.R.M., Ideker, T.: Conserved Patterns of Protein Interaction in Multiple Species. Proc. Nat. Acad. Sci. 102(6), 1974–1979 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dondi, R., Fertin, G., Vialette, S. (2011). Finding Approximate and Constrained Motifs in Graphs. In: Giancarlo, R., Manzini, G. (eds) Combinatorial Pattern Matching. CPM 2011. Lecture Notes in Computer Science, vol 6661. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21458-5_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-21458-5_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21457-8
Online ISBN: 978-3-642-21458-5
eBook Packages: Computer ScienceComputer Science (R0)