nach oben

Theory of Computing Systems

Erschienen in:

01.05.2015

Some Results on More Flexible Versions of Graph Motif

verfasst von: Romeo Rizzi, Florian Sikora

Erschienen in: Theory of Computing Systems | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs

Nächster Artikel New Lower Bounds on Circuit Size of Multi-output Functions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alm, E., Arkin, A.P.: Biological Networks. Curr. Opin. Struct. Biol. 13 (2), 193–202 (2003)CrossRef

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)

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)

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)

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)

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)CrossRefMathSciNet

Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discret. Math. 37 (1), 35–50 (1981)CrossRefMATHMathSciNet

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)CrossRef

Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic and Discret. Methods 3 (2), 214–228 (1982)CrossRefMATHMathSciNet

10.

Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithm 36 (2), 205–240 (2000)CrossRefMATHMathSciNet

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)CrossRef

12.

Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discr. Algo. 9(1), 82–99 (2011)

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)

14.

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)

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)CrossRef

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)

17.

Gagneur, J., Krause, R., Bouwmeester, T., Casari, G.: Modular decomposition of protein-protein interaction networks. Genome Biol. 5 (8), R57 (2004)CrossRef

18.

Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65 (4), 828–844 (2013)CrossRefMATHMathSciNet

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)

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)

21.

Koutis, I.: Constrained multilinear detection for faster functional motif discovery. Inf. Process. Lett. 112 (22), 889–892 (2012)CrossRefMATHMathSciNet

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)CrossRef

23.

Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006)CrossRef

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)CrossRef

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)

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)CrossRef

27.

Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24 (4), 427–433 (2006)CrossRef

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)CrossRefMathSciNet

Titel: Some Results on More Flexible Versions of Graph Motif
verfasst von: Romeo Rizzi
Florian Sikora
Publikationsdatum: 01.05.2015
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9564-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2015

Two-Way Automata Characterizations of L/poly Versus NL

Preface

Omega-Rational Expressions with Bounded Synchronization Delay

On Extracting Space-bounded Kolmogorov Complexity

Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs

Generalized Post Embedding Problems

Premium Partner