Abstract
Protein-protein interaction networks, particularly that of the yeast S. Cerevisiae, have recently been studied extensively. These networks seem to satisfy the small world property and their (1-hop) degree distribution seems to form a power law. More recently, a number of duplication based random graph models have been proposed with the aim of emulating the evolution of protein-protein interaction networks and satisfying these two graph theoretical properties. In this paper, we show that the proposed model of Pastor-Satorras et al. does not generate the power law degree distribution with exponential cutoff as claimed and the more restrictive model by Chung et al. cannot be interpreted unconditionally. It is possible to slightly modify these models to ensure that they generate a power law degree distribution. However, even after this modification, the more general k-hop degree distribution achieved by these models, for k > 1, are very different from that of the yeast proteome network. We address this problem by introducing a new network growth model that takes into account the sequence similarity between pairs of proteins (as a binary relationship) as well as their interactions. The new model captures not only the k-hop degree distribution of the yeast protein interaction network for all k > 0, but it also captures the 1-hop degree distribution of the sequence similarity network, which again seems to form a power law.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. In: Proc. ACM STOC, pp. 171–180. ACM Press, New York (2000)
Aiello, W., Chung, F., Lu, L.: Random evolution in massive graphs. In: Proc. FOCS, pp. 510–519 (2001)
Balakrishnan, R., Christie, K.R., Costanzo, M.C., Dolinski, K., Dwight, S.S., Engel, S.R., Fisk, D.G., Hirschman, J.E., Hong, E.L., Nash, R., Oughtred, R., Skrzypek, M., Theesfeld, C.L., Binkley, G., Lane, C., Schroeder, M., Sethuraman, A., Dong, S., Weng, S., Miyasato, S., Andrada, R., Botstein, D., Cherry, J.M.: Saccharomyces Genome Database (April 1, 2004), ftp://ftp.yeastgenome.org/yeast/
Barabási, A.-L., Albert, R.A.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J.H., Sahinalp, S.C.: The degree distribution of the generalized duplication model. Theoretical Computer Science 369, 234–249 (2006)
Berger, N., Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Degree distribution of the FKP network model. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 725–738. Springer, Heidelberg (2003)
Bhan, A., Galas, D.J., Dewey, T.G.: A duplication growth model of gene expression networks. Bioinformatics 18, 1486–1493 (2002)
Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proc. ACM-SIAM SODA, pp. 132–139. ACM Press, New York (2003)
Bollobás, B., Riordan, O., Spencer, J., Tusanády, G.: The degree sequence of a scale-free random graph process. Random Structures and Algorithms 18, 279–290 (2001)
Chung, F., Lu, L., Dewey, T.G., Galas, D.J.: Duplication models for biological networks. Journal of Computational Biology 10, 677–687 (2003)
Cooper, C., Frieze, A.: A general model of webgraphs. Random Structures and Algorithms 22(3), 311–335 (2003)
Deane, C.M., Salwinski, L., Xenarios, I., Eisenberg, D.: Protein interactions: Two methods for assessment of the reliability of high-throughput observations. Molecular and Cellular Proteomics 1, 349–356 (2002)
Erdös, P., Rényi, A.: On random graphs I. Publicationes Mathematicae Debrecen 6, 290–297 (1959)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-Law Relationships of the Internet Topology. In: SIGCOMM (1999)
Ferrer i Cancho, R., Janssen, C.: The small world of human language. Procs. Roy. Soc. London B 268, 2261–2266 (2001)
Force, A., Lynch, M., Pickett, F.B., Amores, A., Yan, Y., Postlethwait, J.: Preservation of duplicate genes by complementary degenerative mutations. Genetics 151, 1531–1545 (1999)
Han, J.D., Dupuy, D., Bertin, N., Cusick, M., Vidal, M.: Effects of sampling on the predicted topology of interactome networks. Nature Biotechnology 23, 839–844 (2005)
Ispolatov, I., Krapivsky, P.L., Yuryev, A.: Duplication-divergence model of protein interaction network. Physical Review, E 71, 061911 (2005)
Ito, T., et al.: A Comprehensive two-hybrid analysis to explore the yeast protein interactome. PNAS 98(8), 4569 (2001)
Jeong, H., Mason, S., Barabasi, A.-L., Oltvai, Z.N.: Lethality and centrality in protein networks. Nature 411, 41 (2001)
Kleinberg, J., Kumar, R., Raphavan, P.P., Rajagopalan, S., Tomkins, A.: The Web as a graph: Measurements, models and methods. In: Proc. COCOON, Tokyo, Japan, pp. 1–17 (1999)
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proc. FOCS, pp. 57–65 (2000)
Nadeau, J.H., Sankoff, D.: Comparable Rates of Gene Loss and Functional Divergence After Genome Duplications Early in Vertebrate Evolution. Genetics 147, 1259 (1997)
van Noort, V., Snel, B., Huymen, M.A.: The yeast coexpression network has a small-world scale-free architecture and can be explained by a simple model. EMBO Reports 5(3) (2004)
Ohno, S.: Evolution by gene duplication. Springer, Berlin (1970)
Pastor-Satorras, R., Smith, E., Sole, R.V.: Evolving protein interaction networks through gene duplication. J. Theor. Biol. 222, 199–210 (2003)
Pearson, W.R., Lipman, D.J.: Fasta. ftp://ftp.virginia.edu/pub/fasta/ (data of access)
Przulj, N., Corneil, D.G., Jurisica, I.: Modeling Interactome: Scale-Free or Geometric? Bioinformatics 20(18), 3508–3515 (2004)
Redner, S.: How Popular is Your Paper? An Empirical Study of the Citation Distribution. Eur. Phys. Jour. B 4, 131–134 (1998)
Seoighe, C., Wolfe, K.H.: Yeast genome evolution in the post-genome era. Current Opinion in Mol. Biol. 2, 548–554 (1999)
Seoighe, C., Wolfe, K.H.: Updated map of duplicated regions in the yeast genome. Gene 238(1), 253–261 (1999)
Simon, H.A.: On a class of skew distribution functions. Biometrika 42, 425–440 (1955)
Uetz, P.L., et al.: A comprehensive analysis of protein-protein interactions in Saccharomyces Cerevisiae. Nature 403, 623–627 (2000)
Vázquez, A., Flammini, A., Maritan, A., Vespignani, A.: Modelling of protein interaction networks. Complexus 1, 38–44 (2003)
Wagner, A.: The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes. Mol. Biol. Evol. 18, 1283–1292 (2001)
Watts, D.J., Strogatz, S.H.: Colective dynamics of small-world networks. Nature 393, 440–442 (1998)
Wolfe, K.H., Shields, D.C.: Molecular evidence for an ancient duplication of the entire yeast genome. Nature 387, 708–713 (1997)
Xenarios, I., et al.: DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions. Nucleic Acids Res. 30, 303–305 (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J.H., Sahinalp, S.C. (2007). Improved Duplication Models for Proteome Network Evolution. In: Eskin, E., Ideker, T., Raphael, B., Workman, C. (eds) Systems Biology and Regulatory Genomics. RSB RRG 2005 2005. Lecture Notes in Computer Science(), vol 4023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48540-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-48540-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-48293-2
Online ISBN: 978-3-540-48540-7
eBook Packages: Computer ScienceComputer Science (R0)