CENTRALITY METRICS FOR IDENTIFYING NETWORK FRAGILITY IN PROTEIN-PROTEIN INTERACTION NETWORKS AND SYNTHESIZED NK SYSTEMS

Ken A. Hawick

View Full Paper

References

  1. [1] Abdo, A.H., de Moura, A.P.S.: Clustering as a measure of the local topology of networks. Tech. rep., Universidade de São Paulo, University of Aberdeen (February 2006), http: //arxiv.org/abs/physics/0605235v4
  2. [2] Baillie, C.F., Johnston, D.: Damaging 2d quantum gravity. Physics Letters B 326, 51–56 (1994)
  3. [3] Baillie, C., Hawick, K., Johnston, D.: Quenching 2d quantum gravity. Physics Letters B 328(3-4), 284–290 (June 1994)
  4. [4] Barabasi, A.L., Oltvai, Z.N.: Network biology: Understanding the cell’s functional organization. Nature Reviews Genetiocs 5, 101–113 (2004)
  5. [5] Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani, A.: The architecture of complex weighted networks. PNAS 101(11), 3747–3752 (2004), http://www.pnas.org/ cgi/content/abstract/101/11/3747
  6. [6] Blomberg, C.: Physics of Life The Physicist’s Road to Biology. No. ISBN 978-0-444-52798-1, Elsevier (2007) 29
  7. [7] Blossey, R.: Computational Biology A Statistical Mechanics Perspective. No. ISBN 1-58488-556-4, Chapman and Hall (2006)
  8. [8] Brandes, U.: A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25(2), 163–177 (2010)
  9. [9] Butland, G., Peregrin-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 (February 2005)
  10. [10] Caflisch, A.: Protein folding: Simple models for a complex process. Structure 12, 1750–1752 (2004)
  11. [11] Choen, J.: Bioinformatics an introduction for computer scientists. ACM Computing Surveys 36(2), 122–158 (June 2004)
  12. [12] Clauset, A.: Finding local community structure in networks. Phys. Rev. E 72, 026132–1–6 (2005)
  13. [13] Cordero, F., Manini, D., Gribaudo, M., Balbo, G.: A new framework for modeling complex biological systems: user?s manual. Ricercatore Universita degli Studi di Torino, Dipartimento di Informatica, Corso Svizzera 185 10149 Torino (Italy) (2011), http://www.di.unito. it/?manini/OBAM-Tool-Draw/
  14. [14] COSIN: Complexity in networks european project coevolution and self-organization in dynamical networks (cosin). http://www.cosinproject.org/ (August 2011)
  15. [15] Darabos, C., Tomassini, M., Cunto, F.D., Provero, P., Moore, J.H., Giacobini, M.: Toward robust network based complex systems: from evolutionary cellular automata to biological models. Intelligenza Artificiale 5, 37–47 (2011)
  16. [16] Derrida, B., Pomeau, Y.: Random networks of automata: A simple annealed approximation. Europhys. Lett. 1(2), 45–49 (1986)
  17. [17] Derrida, B., Stauffer, D.: Phase transitions in twodimensional Kauffman cell automata. Europhys. Lett. 2, 739 (1986)
  18. [18] Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik 1, 269–271 (1959)
  19. [19] Dijkstra, E.: A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1(1), 269–271 (1959)
  20. [20] Ebden, J.H., Phillips, C.A., Rogers, G.L., Langston, M.A.: The maximum clique enumeration problem: Algorithms, applications and implementations. In: Proc. ISBRA 2011. pp. 306–319. No. 6674 in LNBI, Springer (2011)
  21. [21] ElisabethWong, Baur, B., Quader, S., Huang, C.H.: Biological network motif detection: principles and practice. Briefings in Bioinformatics June, 1–14 (2011)
  22. [22] Everett, M., Borgatti, S.P.: Ego network betweenness. Social Networks 27, 31–38 (2005)
  23. [23] Fenyo, D. (ed.): Computational Biology. No. ISBN 978160-7618-416, Springer, NY, USA. (2010)
  24. [24] Ferraro, N., Palopoli, L., Panni, S., Rombo, S.E.: Asymmetric comparison and querying of biological networks. IEEE/ACM Trans. Computational Biology and Bioinformatics 8, 876–889 (2011)
  25. [25] Floyd, R.W.: Algorithm 97: Shortest Path. Communications of the ACM 5(6), 345 (1962)
  26. [26] Freeman, L.C.: Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1978)
  27. [27] Freeman, L.C., Borgatti, S.P., White, D.R.: Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks 13, 141–154 (1991)
  28. [28] Gershenson, C.: Introduction to random boolean networks. Tech. Rep. arXiv.org:nlin/0408006v3, Vrije Universiteit Brussel (August 2004)
  29. [29] Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99, 7821–7826 (2002)
  30. [30] Goldberg, A.V.: A simple shortest path algorithm with linear average time. In: Proc. 9th Annual European Symposium on Algorithms. pp. 230–241 (2001)
  31. [31] Hagburg, A., Schult, D., Swart, P.: NetworkX Reference (4 August 2013), https://networkx.github.io/, release 1.8.1
  32. [32] Harvey, I., Bossomaier, T.: Time out of joint: Attractors in asynchronous random boolean networks. In: Husbands, P., Harvey, I. (eds.) Proc Fourth European Conference on Artificial Life (ECAL97). pp. 67–75. MIT Press (1997)
  33. [33] Hawick, K.A.: Eigenvalue spectra measurements of complex networks. In: H.Arabnia (ed.) Proc. Int. Conf on Scientific Computing (CSC’08). pp. 174–179. CSREA, Las Vegas (14-17 July 2008)
  34. [34] Hawick, K.A.: Detecting and labelling wireless community network structures from eigen-spectra. In: Proc. International Conference on Wireless Networks (ICWN’10). pp. 398–404. WorldComp, Las Vegas, USA (12-15 July 2010), iCW5189
  35. [35] Hawick, K.A.: Interactive Graph Algorithm Visualization and the GraViz Prototype. Tech. Rep. CSTN-061, Computer Science, Massey University, Albany, North Shore 102-904, Auckland, New Zealand (October 2010), www.massey. ac.nz/˜kahawick/cstn/061/cstn-061.pdf
  36. [36] Hawick, K.A.: Applying enumerative, spectral and hybrid graph analyses to biological network data. In: Int. Conf. on Computational Intelligence and Bioinformatics (CIB 2011). pp. 89–96. IASTED, Pittsburgh, USA (7-9 November 2011)
  37. [37] Hawick, K.A.: Betweenness centrality metrics for assessing electrical power network robustness against fragmentation and node failure. In: Proc. International Conference on Power and Energy Systems (EuroPES 2012). pp. 186–193. IASTED, Napoli, Italy. (25-27 June 2012)
  38. [38] Hawick, K.A.: Node-failure and islanding in national grid scale electricity distribution networks. In: Proc. Int. Conf. Power and Energy Systems and Applications. pp. 52–58. IASTED, Las Vegas (12-14 November 2012)
  39. [39] Hawick, K.A.: Water distribution network robustness and fragmentation using graph metrics. In: Proc. Int. Conf. on Water Resource Management (AfricaWRM 2012). pp. 304–310. No. 762-037, IASTED, Gabarone, Botswana (3-5 September 2012), cSTN-158
  40. [40] Hawick, K.A., James, H.A.: Managing community membership information in a small-world grid. Research Letters in the Information and Mathematical Sciences 7(CSTN002), 101–115 (March 2005), iSSN 1175-2777
  41. [41] Hawick, K.A., James, H.A.: Node importance ranking and scaling properties of some complex road networks. Tech. Rep. CSTN-021, Computer Science, Massey University, Albany, North Shore 102-904, Auckland, New Zealand (August 2005)
  42. [42] Hawick, K.A., James, H.A., Scogings, C.J.: Structural Circuits and Attractors in Kauffman Networks. In: Abbass, H.A., Randall, M. (eds.) Proc. Third Australian Conference 30 on Artificial Life. LNCS, vol. 4828, pp. 189–200. Springer, Gold Coast, Australia (4-6 December 2007), 978-3-54076930-9
  43. [43] Hawick, K.A., Leist, A., Playne, D.P.: Parallel Graph Component Labelling with GPUs and CUDA. Parallel Computing 36(12), 655–678 (December 2010), www.elsevier. com/locate/parco
  44. [44] Hines, P., Blumsack, S.: A centrality measure for electrical networks. In: Proc. 41st Hawaii Int. Conf. on System Sciences. pp. 1–8. HICSS, Hawaii, Big Island (7-10 January 2008)
  45. [45] Jamil, H.: Computing subgraph isomorphic queries using structural unification and minimum graph structures. In: Proc. SAC 2011, Taichung, Taiwan. pp. 1053–1058 (2011)
  46. [46] Joy, M.P., Brock, A., Ingber, D.E., Huang, S.: Highbetweenness proteins in the yeast protein interaction network. Journal of Biomedecine and Biotechnology 2, 96–103 (2005)
  47. [47] Kadanoff, L., Coppersmith, S., Aldana, M.: Boolean dynamics with random couplings. In: Kaplan, E., Marsden, J., Sreenivasan, K. (eds.) Perspectives and Problems in Nonlinear Science. Springer (2003)
  48. [48] Kauffman, S.A.: The Origins of Order. Oxford University Press (1993)
  49. [49] Kauffman, S., Peterson, C., Samuelsson, B., Troein, C.: Random boolean network models and the yeast transcriptional network. Proc. Natl. Acad. Sci. USA 100, 14796 (2003)
  50. [50] Mattiussi, C., Durr, P., Marbach, D., Floreano, D.: Beyond graphs: A new synthesis. Journal of Computational Science 2, 165–177 (2011)
  51. [51] Mueller, L.A.J., Kugler, K.G., Dander, A., Graber, A., Dehmer, M.: Quacn: an r package for analyzing complex biological networks quantitatively. Bioinformatics 27, 140– 141 (2011)
  52. [52] Muff, S., Rao, F., Caflisch, A.: Local modularity measure for network clusterizations. Phys. Rev. E 72, 056107 (2005)
  53. [53] Nacher, J.C., Ueda, N., Yamada, T., Kanehisa, M., Akutsu, T.: Study on the clustering coeffcients in metabolic network using a hierarchical framework. In: Fourth International Workshop on Bioinformatics and Systems Biology. pp. 34–35. Kyoto, Japan (31 May 3 June 2004)
  54. [54] Nepusz, T., Setany, P.P.: iGraph. Budapest, Hungary (4 February 2014), http://igraph.org/python/ doc/python-igraph.pdf, version 0.7.0
  55. [55] Newman, M.E.J.: Models of the small world: A review. Journal of Statistical Physics 101, 819–841 (2000)
  56. [56] Newman, M., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)
  57. [57] Pal, D., Rao, P.R.: A tool for fast indexing and querying of graphs. In: Proc. Int. World Wide Web Conf. (IW3C2), Hyderabad, India, 2011. pp. 241–244 (28 March 1 April 2011)
  58. [58] Prim, R.: Shortest connection networks and some generalizations. The Bell System Technical Journal November, 1389–1401 (1957)
  59. [59] Rao, F., Caflisch, A.: The protein folding network. J. Mol. Biol. 342, 299–306 (2004)
  60. [60] Rao, F.: Theoretical and Computational Studies of Protein Folding Energy Landscapes. Ph.D. thesis, University of Zurich (2005)
  61. [61] Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N., Barabasi, A.L.: Hierarchical organization of modularity in metabolic networks. Science 297, 1551–1555 (2002)
  62. [62] Samatova, N.F., Schmidt, M.C., Hendrix, W., Breimyer, P., Thomas, K., Park, B.H.: Coupling graph perturbation theory with scalable parallel algorithms for large-scale enumeration of maximal cliques in biological graphs. Journal of Physics: Conf. Series 125, 012053–1–7 (2008)
  63. [63] Schank, T., Wagner, D.: Approximating clustering coeficient and transitivity. Journal of Graph Algorithms ad Applications 9(2), 265–275 (2005)
  64. [64] Schietgat, L.: Graph-based data mining for biological applications. AI Communications 24, 95–96 (2011)
  65. [65] Settanni, G., Fersht, A.R.: High temperature unfolding simulations of the trpz1 peptide. Biophys J. BioFAST 94(11), 4444–4453 (June 2008)
  66. [66] Sevon, P., Eronen, L., Hintsanen, P., Kulovesi, K., Toivonen, H.: Link discovery in graphs derived from biological databases. In: Proc. 3rd Int. Workshop on Data Integration in the Life Sciences (DILS 2006). pp. 35–49 (2006)
  67. [67] Team, J.D.: Java Universal Graph/Network Framework (JUNG2) (22 April 2009), http://sourceforge. net/apps/trac/jung/wiki/JUNGManual, version 2.0
  68. [68] Tizghadam, A., Leon-Garcia, A.: Betweenness centrality and resistance distance in communication networks. IEEE Network Nov/Dec, 10–16 (2010)
  69. [69] Toivonen, H., Zhou, F., Hartikainen, A., Hinkka, A.: Compression of weighted graphs. In: Proc. 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), San Diego, CA, USA. pp. 1–9 (August 2011)
  70. [70] UCLA: Database of interacting proteins (dip). http:// dip.doe-mbi.ucla.edu/dip/ (August 2011)
  71. [71] Wolfram, S.: Theory and Applications of Cellular Automata. World Scientific (1986)
  72. [72] Wuchty, S., Ravasz, E., Barabasi, A.L.: The architecture of biological networks. In: Proc. Complex Systems in Biomedecine. pp. 1–30. Kluwer (2003)
  73. [73] Yang, M., Li, R., Chu, T.: Construction of a boolean model of gene and protein regulatory network with memory. Neural Networks 52, 18–24 (2014)
  74. [74] yWorks: yed java graph editor (2008), http://www. yworks.com/
  75. [75] Zertuche, F.: On the robustness of nk-kauffman networks against changes in their connections and boolean functions. J. Math. Phys. 50, 043513 (2009)
  76. [76] Zgeng, G., Jiang, M., He, X., Zhao, J., Guo, H., Chen, G., Zha, Q., Lu, A.: Discrete derivative: a data slicing algorithm for exploration of sharing biological networks between rheumatoid arthritis and coronary heart disease. BioData Mining 4, 1–21 (2011), www.biodatamining. org/content/4/1/18
  77. [77] Zhou, W., Nakhleh, L.: Properties of metabolic graphs: biological organization or representation artifacts? BMC Bioinformatics 12, 1–12 (2011)
  78. [78] Zhou, Z.: Using expansion algorithm to identify protein from biological networks. Journal of Convergence Information Technology 6, 63–69 (2011)
  79. [79] Zhu, L., Ng, W.K., Cheng, J.: Structure and attribute index for approximate graph matching in large graphs. Information Systems 36, 958–972 (2011)

Important Links:

Go Back