We have studied the structural properties of the yeast protein interaction networks and the transport phenomena along the shortest pathways on biocomplex networks from the graph theoretic viewpoint. Thanks to recent development of data collection and graph analysis methods, the structural properties of the yeast protein interaction networks have been unveiled rapidly. Here we analyzed the degree distribution, the degree-degree correlation, and the clustering coefficient of the yeast interaction networks for several different datasets available9,24'25,27'31 and also for an integrated data we constructed. The yeast PIN is found to be strongly dissortative and highly modular. We believe that such analysis could be helpful for understanding the evolution of the protein interaction networks and finding protein interactions yet undiscovered. Moreover, we investigate the transport problem along the shortest pathways on biocomplex networks such as metabolic networks. We found that the load distribution follows a power law, and its exponent is robust, insensitive to detailed structural properties. We could classify real-world networks into two classes based on this property and also on the topological features of the shortest pathways. In particular, we find the metabolic networks for archaea belongs to the different class from that for bacteria and eukaryotes. The shortest pathway structure is simple for archaea. While further theoretical understandings are needed in relation to the robustness of the load distribution, at the moment, it would be interesting to notice that the load distribution is closely related to the structure of the core part of biocomplex networks.
This work is supported by the KOSEF Grant No. R14-2002-059-01000-0 in the ABRL program.
1. Ziemelis K, Allen L. Complex systems, and following review articles on complex systems. Nature 2001; 410:241.
2. Gallagher R, Appenzeller T. Complex systems, and following viewpoint articles on complex systems. Science 1999; 284:87.
3. Strogatz SH. Exploring complex networks. Nature 2001; 410:268-276.
4. Albert R, Barabási A-L. Statistical mechanics of complex networks. Rev Mod Phys 2002; 74:47.
5. Dorogovtsev SN, Mendes JFF. Evolution of networks. Oxford: Oxford University Press, 2003.
6. Newman MEJ. The structure and function of complex networks. SIAM Rev 2003; 45:167.
7. Gavin AC et al. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 2002; 415:141-147.
8. Marcotte EM et al. A combined algorithm for genome-wide prediction of protein function. Nature 1999; 402:83-86.
9. Uetz P et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature 2000; 403:623-627.
10. Erdos P, Rényi A. On the evolution of random graph. Publ Math Inst Hung Acad Sci Ser A 1960; 5:17.
11. Barabási A-L, Albert R, Jeong H. Mean-field theory of scale-free networks. Physica A 1999; 272:173.
12. Albert R, Jeong H, Barabási A-L. Diameter of the world wide web. Nature 1999; 401:130-131.
13. Huberman BA, Adamic LA. Growth dynamics of the world wide web. Nature 1999; 401:131.
14. Broder A et al. Graph structure of the world wide web. Computer Networks 2000; 33:309.
15. Faloutsos M. Faloutsos P, Faloutsos C. On power-law relationship in the internet topology. Comput Commun Rev 1999; 29:251.
16. Pastor-Satorras R, Vázquez A, Vespignani A. Dynamical and correlation properties of the Internet. Phys Rev Lett 2001; 87:258701.
17. Goh K-I, Kahng B, Kim D. Fluctuation-driven dynamics of the Internet topology. Phys Rev Lett 2002; 88:108701.
18. Redner S. How popular is your paper? Eur Phys J B 1998; 4:131.
19. Newman MEJ. The structure of scientific collaboration. Proc Natl Acad Sci USA 2001; 98:404.
20. Barabási A-L, Jeong H, Ravasz R ct al. On the topology of the scientific collaboration networks. Physica A 2002; 311:590-614.
21. Jeong H, Tombor B, Albert R et al. Large-scale organization of metabolic networks. Nature 2000; 407:651.
22. Ravasz E et al. Hierachical organization of modularity in metabolic networks. Science 2002; 297:1551-1555.
23. Ravasz E, Barabási A-L. Hierachical organization in complex networks. Phys Rev E 2003; 67:026112.
24. Mews HW et al. MIPS: Analysis and annotation of proteins from whole genomes. Nucl Acids Res 2004; 32:D41-D44.
25. Salwinski L et al. The database of interacting proteins: 2004 update. Nucl Acids Res 2004; 32:D449-D451.
26. Bader GD, Betel D, Hogue CW. BIND: The biomolecular interaction network database. Nucl Acids Res 2003; 31:248-250.
27. Ito T et al. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc Natl Acad Sci USA 2001; 98:4569-4574.
28. Schwikowski B, Uetz P, Fields S. A network of protein-protein interactions in yeast. Nat Biotechnol 2000; 18:1257-1261.
29. Tong AH et al. A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules. Science 2002; 295:321-324.
30. Ho Y et al. Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature 2002; 415:180-183.
31. Jeong H et al. Lethality and centrality in protein networks. Nature 2001; 411:41-42.
32. Wagner A. How the global structure of protein interaction networks evolves. Proc R Soc Lond B 2003; 270:457-466.
33. Newman MEJ. Assortative mixing in networks. Phys Rev Lett 2002; 89:208701.
34. Maslov S, Sneppen K. Specificity and stability in topology of protein networks. Science 2002; 296:910-913.
35. Goh K-I, Kahng B, Kim D. Universal behavior of load distribution in scale-free networks. Phys Rev Lett 2001; 87:278701.
36. Freeman LC. A set of measure of centrality based on betweenness. Sociometry 1977; 40:35.
37. Newman MEJ. Scientific collaboration networks II: Shortest paths, weighted networks, and centrality. Phys Rev E 2001; 64:016132.
38. Brandes U. A faster algorithm for betweenness centrality. J Math Sociol 2001; 25:163.
39. Goh K-I, Kahng B, Kim D. Packet transport and load distribution in scale-free network models. Physica A 2003; 318:72.
40. Goh K-I, Oh E, Jeong H et al. Classification of scale-free networks. Proc Natl Acad Sci USA 2002; 99:12583.
41. Barabási A-L, Albert R. Emergence of scaling in random networks. Science 1999; 286:509.
42. Solé R, Pastor-Satorras R, Smith E et al. A model of large-scale proteome evolution. Adv Complex Syst 2002; 5:43.
43. Meyer D. University of Oregon Route Views Archive Project 2001 (http://archive.routeviews.org).
44. Jung S, Kim S, Kahng B. Geometric fractal growth model for scale-free networks. Phys Rev E 2002; 65:056101.
Was this article helpful?