Some results on more flexible versions of Graph Motif. (English) Zbl 1316.05048
Summary: 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 NP-complete, it allows algorithms in FPT for biologically relevant parameterizations.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 68Q25 | Analysis of algorithms and problem complexity |
| 92C42 | Systems biology, networks |
References:
| [1] | Alm, E., Arkin, A.P.: Biological Networks. Curr. Opin. Struct. Biol. 13 (2), 193-202 (2003) · doi:10.1016/S0959-440X(03)00031-9 |
| [2] | 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.): Proceedings of the 5th International Symposium Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science, vol. 6478, pp. 14-25. Springer, Berlin (2010) · Zbl 1309.68143 |
| [3] | 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.): Proceedings of the 19th Annual Symposium Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 5029, pp. 31-43. Springer, Berlin (2008) · Zbl 1143.68501 |
| [4] | Björklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: Portier, N.,Wilke, T. (eds.): Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 20, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012) · Zbl 1354.68108 |
| [5] | Böcker, S., Rasche, F., Steijger, T.: Annotating Fragmentation Patterns. In: Salzberg, S., Warnow, T. (eds.) Proceedings of the 9th International Workshop Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science, Vol. 5724, pp 13-24. Springer, Berlin Heidelberg New York (2009) |
| [6] | Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-Free Querying of Protein Interaction Networks. J. Comput. Biol. 17 (3), 237-252 (2010) · doi:10.1089/cmb.2009.0170 |
| [7] | Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discret. Math. 37 (1), 35-50 (1981) · Zbl 0478.05071 · doi:10.1016/0012-365X(81)90138-2 |
| [8] | Costanzo, M., Baryshnikova, A., Bellay, J., Kim, Y., Spear, E.D., Sevier, C.S., Ding, H., Koh, J.L.Y., Toufighi, K., Mostafavi, S., Prinz, J., St. Onge, R.P., VanderSluis, B., Makhnevych, T., Vizeacoumar, F.J., Alizadeh, S., Bahr, S., Brost, R.L., Chen, Y., Cokol, M., Deshpande, R., Li, Z., Lin, Z.Y., Liang, W., Marback, M., Paw, J., San Luis, B.J., Shuteriqi, E., Tong, A.H., van Dyk, N., Wallace, I.M., Whitney, J.A., Weirauch, M.T., Zhong, G., Zhu, H., Houry, W.A., Brudno, M., Ragibizadeh, S., Papp, B., Pál, C., Roth, F.P., Giaever, G., Nislow, C., Troyanskaya, O.G., Bussey, H., Bader, G.D., Gingras, A.C., Morris, Q.D., Kim, P.M., Kaiser, C.A., Myers, C.L., Andrews, B.J., Boone, C.: The genetic landscape of a cell. Sci. 327 (5964), 425-431 (2010) · doi:10.1126/science.1180823 |
| [9] | Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic and Discret. Methods 3 (2), 214-228 (1982) · Zbl 0497.05031 · doi:10.1137/0603021 |
| [10] | Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithm 36 (2), 205-240 (2000) · Zbl 0961.68152 · doi:10.1006/jagm.2000.1090 |
| [11] | Del Mondo, G., Eveillard, D., Rusu, I.: Homogeneous decomposition of protein interaction networks: refining the description of intra-modular interactions. Bioinformatics 25 (7), 926-932 (2009) · doi:10.1093/bioinformatics/btp083 |
| [12] | Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discr. Algo. 9(1), 82-99 (2011) · Zbl 1222.05053 |
| [13] | Dondi, R., Fertin, G., Vialette, S.: Finding Approximate and Constrained Motifs in Graphs. In: Giancarlo, R., Manzini, G. (eds.) Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, Vol. 6661, pp 388-401. Springer, Berlin Heidelberg New York (2011) · Zbl 1339.92025 |
| [14] | Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013) · Zbl 1358.68006 |
| [15] | Edwards, A.M., Kus, B., Jansen, R., Greenbaum, D., Greenblatt, J., Gerstein, M.: Bridging structural biology and genomics: assessing protein interaction data with known complexes. Trends Genet. 18 (10), 529-536 (2002) · doi:10.1016/S0168-9525(02)02763-4 |
| [16] | Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol. 4596, pp 340-351. Springer, Poland (2007) · Zbl 1171.68497 |
| [17] | Gagneur, J., Krause, R., Bouwmeester, T., Casari, G.: Modular decomposition of protein-protein interaction networks. Genome Biol. 5 (8), R57 (2004) · doi:10.1186/gb-2004-5-8-r57 |
| [18] | Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65 (4), 828-844 (2013) · Zbl 1263.05029 · doi:10.1007/s00453-011-9600-8 |
| [19] | Habib, M., Montgolfier, F.d., Paul, C.: A Simple Linear-TimeModular Decomposition Algorithm for Graphs, Using Order Extension. In: Hagerup, T., Katajainen, J. (eds.): Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 3111, pp. 187-198. Springer, Berlin (2004) · Zbl 1095.68622 |
| [20] | Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability, In: Proceedings of the 35th Annual IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 819-830 (1994) · Zbl 0915.68068 |
| [21] | Koutis, I.: Constrained multilinear detection for faster functional motif discovery. Inf. Process. Lett. 112 (22), 889-892 (2012) · Zbl 1248.68583 · doi:10.1016/j.ipl.2012.08.008 |
| [22] | Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinforma. (TCBB) 3 (4), 360-368 (2006) · doi:10.1109/TCBB.2006.55 |
| [23] | Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006) · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001 |
| [24] | Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N., Barabasi, A.L.: Hierarchical Organization of Modularity in Metabolic Networks. Sci. 297 (5586), 1551-1555 (2002) · Zbl 1025.57011 · doi:10.1126/science.1073374 |
| [25] | Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, In: Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC), pp. 475-484. ACM (1997) · Zbl 0963.68175 |
| [26] | Segal, E., Shapira, M., Regev, A., Pe’er, D., Botstein, D., Koller, D., Friedman, N.: Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data. Nat. Genet. 34 (2), 166-176 (2003) · doi:10.1038/ng1165 |
| [27] | Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24 (4), 427-433 (2006) · doi:10.1038/nbt1196 |
| [28] | Sikora, F.: Aspects algorithmiques de la comparaison d’éléments biologiques. Ph.D. thesis, Université Paris-Est. (in French) (2011) |
| [29] | Zuckerman, D.: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory Comput. 3 (1), 103-128 (2007) · Zbl 1213.68322 · doi:10.4086/toc.2007.v003a006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
