Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Enhanced Multiobjective Population-Based Incremental Learning with Applications in Risk Treaty Optimization Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

On Combinatorial Optimisation in Analysis of Protein-Protein Interaction and Protein Folding Networks

verfasst von : David Chalupa

Erschienen in: Applications of Evolutionary Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Protein-protein interaction networks and protein folding networks represent prominent research topics at the intersection of bioinformatics and network science. In this paper, we present a study of these networks from combinatorial optimisation point of view. Using a combination of classical heuristics and stochastic optimisation techniques, we were able to identify several interesting combinatorial properties of biological networks of the COSIN project. We obtained optimal or near-optimal solutions to maximum clique and chromatic number problems for these networks. We also explore patterns of both non-overlapping and overlapping cliques in these networks. Optimal or near-optimal solutions to partitioning of these networks into non-overlapping cliques and to maximum independent set problem were discovered. Maximal cliques are explored by enumerative techniques. Domination in these networks is briefly studied, too. Applications and extensions of our findings are discussed.

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 "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

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
Vorheriges Kapitel Evolutionary Multiobjective Optimization for Portfolios in Emerging Markets: Contrasting Higher Moments and Median Models
Nächstes Kapitel A Multi-objective Genetic Programming Biomarker Detection Approach in Mass Spectrometry Data
Literatur
1.
Boyer, F., Morgat, A., Labarre, L., Pothier, J., Viari, A.: Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data. Bioinformatics 21(23), 4209–4215 (2005)CrossRef
2.
Gao, L., Sun, P., Song, J.: Clustering algorithms for detecting functional modules in protein interaction networks. J. Bioinform. Comput. Biol. 7(1), 217–242 (2009)CrossRef
3.
Cohen, J.: Bioinformatics - an introduction for computer scientists. ACM Comput. Surv. 36(2), 122–158 (2004)CrossRef
4.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)MATH
5.
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
6.
7.
Halldórsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145–163 (1997)MathSciNetCrossRefMATH
8.
Chalupa, D.: Construction of near-optimal vertex clique covering for real-world networks. Computing and Informatics (to appear)
9.
10.
Culberson, J.C., Luo, F.: Exploring the k-colorable landscape with iterated greedy. In: Johnson, D.S., Trick, M. (eds.) Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, pp. 245–284. American Mathematical Society, RI (1995)
11.
12.
Atias, N., Sharan, R.: Comparative analysis of protein networks: hard problems, practical solutions. Commun. ACM 55(5), 88–97 (2012)CrossRef
13.
Kuchaiev, O., Stevanović, A., Hayes, W., Pržulj, N.: Graphcrunch 2: software tool for network modeling, alignment and clustering. BMC Bioinf. 12(1), 24 (2011)CrossRef
14.
Gavin, A.C., Aloy, P., Grandi, P., Krause, R., Boesche, M., Marzioch, M., Jensen, C.R.L.J., Bastuck, S., Dümpelfeld, B., et al.: Proteome survey reveals modularity of the yeast cell machinery. Nature 440(7084), 631–636 (2006)CrossRef
15.
Zaki, N., Berengueres, J., Efimov, D.: Prorank: a method for detecting protein complexes. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, pp. 209–216. ACM (2012)
16.
Li, X., Wu, M., Kwoh, C.K., Ng, S.K.: Computational approaches for detecting protein complexes from protein interaction networks: a survey. BMC Genomics 11(Suppl. 1), S3 (2010)CrossRef
17.
Pizzuti, C., Rombo, S.E., Marchiori, E.: Complex detection in protein-protein interaction networks: a compact overview for researchers and practitioners. In: Giacobini, M., Vanneschi, L., Bush, W.S. (eds.) EvoBIO 2012. LNCS, vol. 7246, pp. 211–223. Springer, Heidelberg (2012)CrossRef
18.
Pizzuti, C., Rombo, S.E.: Algorithms and tools for protein-protein interaction networks clustering, with a special focus on population-based stochastic methods. Bioinformatics 30(10), 1343–1352 (2014)CrossRef
19.
Becker, E., Robisson, B., Chapple, C.E., Guénoche, A., Brun, C.: Multifunctional proteins revealed by overlapping clustering in protein interaction network. Bioinformatics 28(1), 84–90 (2006)CrossRef
20.
Adamcsek, B., Palla, G., Farkas, I.J., Derényi, I., Vicsek, T.: CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics 22(8), 1021–1023 (2012)CrossRef
21.
Li, X.L., Tan, S.H., Foo, C.S., Ng, S.K.: Interaction graph mining for protein complexes using local clique merging. Genome Inf. 16(2), 260–269 (2005)
22.
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99(12), 7821–7826 (2002)MathSciNetCrossRefMATH
23.
Cho, Y.R., Hwang, W., Zhang, A.: Identification of overlapping functional modules in protein interaction networks: information flow-based approach. In: Sixth IEEE International Conference on Data Mining Workshops, ICDM Workshops 2006, pp. 147–152 (2006)
24.
Hawick, K.A.: Applying enumerative, spectral and hybrid graph analyses to biological network data. In: International Conference on Computational Intelligence and Bioinformatics (CIB 2011), pp. 89–96. IASTED, Pittsburgh, USA, 7–9 November 2011
25.
Sun, J., Xie, Y., Zhang, H., Faloutsos, C.: Less is more: sparse graph mining with compact matrix decomposition. Stat. Anal. Data Min. 1(1), 6–22 (2008)MathSciNetCrossRef
26.
King, A.D., Pržulj, N., Jurisica, I.: Protein complex prediction via cost-based clustering. Bioinformatics 20(17), 3013–3020 (2004)CrossRef
27.
Pizzuti, C., Rombo, S.E.: Experimental evaluation of topological-based fitness functions to detect complexes in PPI networks. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, pp. 193–200. ACM (2012)
28.
Pizzuti, C., Rombo, S.E.: A coclustering approach for mining large protein-protein interaction networks. IEEE/ACM Trans. Comput. Biol. Bioinf. (TCBB) 9(3), 717–730 (2012)CrossRef
29.
Leskovec, J., Lang, K.J., Mahoney, M.W.: Empirical comparison of algorithms for network community detection. In Rappa, M., Jones, P., Freire, J., Chakrabarti, S. (eds.) Proceedings of the 19th International Conference on World Wide Web, WWW 2010, pp. 631–640. ACM, New York, NY (2010)
30.
Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012)CrossRef
31.
Brohee, S., Helden, J.V.: Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinf. 7(1), 488 (2006)CrossRef
32.
33.
Šíma, J., Schaeffer, S.E.: On the NP-completeness of some graph cluster measures. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 530–537. Springer, Heidelberg (2006)
34.
Rao, F., Caflisch, A.: The protein folding network. J. Mol. Biol. 342(1), 299–306 (2004)CrossRef
35.
Hawick, K.A.: Centrality metrics for comparing protein-protein interaction networks with synthesized NK systems. In: Proceedings of the IASTED International Conference on Biomedical Engineering, pp. 1–8. IASTED, Zurich, Switzerland, 23–25 June 2014
36.
37.
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015)MathSciNetCrossRef
38.
Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10(1), 85–86 (1967)CrossRefMATH
39.
Galinier, P., Hamiez, J.-P., Hao, J.-K., Porumbel, D.: Recent advances in graph vertex coloring. In: Zelinka, I., Snasel, V., Abraham, A. (eds.) Handbook of Optimization: From Classical to Modern Approach. ISRL, vol. 38, pp. 505–528. Springer, Heidelberg (2013)CrossRef
40.
Morgenstern, C.: Improved implementations of dynamic sequential coloring algorithms. Technical report CoSc-91-4, Department of Computer Science, Texas Christian University (1991)
41.
42.
Culberson, J.C.: Iterated greedy graph coloring and the difficulty landscape. Technical report TR92-07, University of Alberta (1992)
43.
Pavlopoulos, G.A., Secrier, M., Moschopoulos, C.N., Soldatos, T.G., Kossida, S., Aerts, J., Schneider, R., Bagos, P.G., et al.: Using graph theory to analyze biological networks. BioData Min. 4(10), 1–27 (2011)
44.
Butland, G., Peregrín-Alvarez, J.M., Li, J., Yang, W., Yang, X., Canadien, V., Starostine, A., Richards, D., Beattie, B., Krogan, N., Davey, M., Parkinson, J., Greenblatt, J., Emili, A.: Interaction network containing conserved and essential protein complexes in Escherichia coli. Nature 433, 531–537 (2005)CrossRef
45.
46.
Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol. 6506, pp. 403–414. Springer, Heidelberg (2010)CrossRef
47.
Kovács, I.A., Palotai, R., Szalay, M.S., Csermely, P.: Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics. PloS ONE 5(9), e12528 (2010)CrossRef
48.
Potluri, A., Singh, A.: Two hybrid meta-heuristic approaches for minimum dominating set problem. In: Panigrahi, B.K., Suganthan, P.N., Das, S., Satapathy, S.C. (eds.) SEMCCO 2011, Part II. LNCS, vol. 7077, pp. 97–104. Springer, Heidelberg (2011)CrossRef
Metadaten
Titel
On Combinatorial Optimisation in Analysis of Protein-Protein Interaction and Protein Folding Networks
verfasst von
David Chalupa
Copyright-Jahr
2016
Buch
Applications of Evolutionary Computation

Print ISBN: 978-3-319-31203-3

Electronic ISBN: 978-3-319-31204-0

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-31204-0_7

Premium Partner

    Bildnachweise