Access by Xinjiang University

Duplication-divergence model of protein interaction network

I. Ispolatov^1,*, P. L. Krapivsky^2,†, and A. Yuryev^1,‡

¹Ariadne Genomics Inc., Rockville, Maryland 20850, USA
²Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA

^*Electronic address: iispolat@lauca.usach.cl;Permanent address: Departamento de Fisica, Universidad de Santiago de Chile, Casilla 302, Correo 2, Santiago, Chile.
^†Electronic address: paulk@bu.edu
^‡Electronic address: ayuryev@ariadnegenomics.com

Phys. Rev. E 71, 061911 – Published 22 June, 2005

DOI: https://doi.org/10.1103/PhysRevE.71.061911

Abstract

We investigate a very simple model describing the evolution of protein-protein interaction networks via duplication and divergence. The model exhibits a remarkably rich behavior depending on a single parameter, the probability to retain a duplicated link during divergence. When this parameter is large, the network growth is not self-averaging and an average node degree increases algebraically. The lack of self-averaging results in a great diversity of networks grown out of the same initial condition. When less than a half of links are (on average) preserved after divergence, the growth is self-averaging, the average degree increases very slowly or tends to a constant, and a degree distribution has a power-law tail. The predicted degree distributions are in a very good agreement with the distributions observed in real protein networks.

Article Text

References (32)

S. Ohno, Evolution by Gene Duplication (Springer-Verlag, New York, 1970).
W.-H. Li, Molecular Evolution (Sinauer, Sunderland, MA, 1999).
L. Patthy, Protein Evolution (Blackwell Publishers, Portland, OR, 1999).
J. S. Taylor and J. Raes, Annu. Rev. Genet. 9, 615 (2004).
A. Wagner, Proc. R. Soc. London, Ser. B 270, 457 (2003).
G. C. Conant and A. Wagner, Genome Res. 13, 2052 (2003).
R. V. Solé, R. Pastor-Satorras, E. D. Smith, and T. Kepler, Adv. Complex Syst. 5, 43 (2002).
J. Kim, P. L. Krapivsky, B. Kahng, and S. Redner, Phys. Rev. E 66, 055101 (2002).
F. Chung, L. Lu, T. G. Dewey, and D. J. Galas, J. Comput. Biol. 10, 677 (2003).
R. Pastor-Satorras, E. Smith, and R. V. Solé, J. Theor. Biol. 222, 199 (2003).
N. V. Dokholyan, B. Shakhnovich, and E. I. Shakhnovich, Proc. Natl. Acad. Sci. U.S.A. 99, 14132 (2002).
A. Vázquez, A. Flammini, A. Maritan, and A. Vespignani, ComPlexUs 1, 38 (2003).
M. Bauer and D. Bernard, J. Stat. Phys. 111, 703 (2003).
C. Coulomb and M. Bauer, Eur. Phys. J. B 35, 377 (2003).
P. L. Krapivsky and B. Derrida, Physica A 340, 714 (2004).
http://www.ariadnegenomics.com/.
S. Novichkova, S. Egorov, and N. Daraselia, Bioinformatics 19, 1699 (2003).
http://www.ariadnegenomics.com/products/pathway.html.
A. Raval, Phys. Rev. E 68, 066119 (2003).
F. Eggenberger and G. Pólya, Z. Angew. Math. Mech. 3, 279 (1923).
N. L. Johnson and S. Kotz, Urn Models and their Applications (Wiley, New York, 1977).
K. Sigmund, Games of Life (Oxford University Press, Oxford, 1993).
A. Bagchi and A. K. Pal, SIAM J. Algebraic Discrete Methods 6, 394 (1985).
D. Aldous, B. Flannery, and J. L. Palacios, Prob. Eng. Infor. Sci. 2, 293 (1988).
S. Kotz, H. Mahmoud, and P. Robert, Stat. Probab. Lett. 49, 163 (2000).
P. Flajolet, J. Gabarró, and H. Pekari, arXivmath.PR/0407098
H. A. Simon, Biometrika 42, 425 (1955); Infect. Control 3, 80 (1960).
We used the identity $\sum_{s ⩾ k} (_{k}^{s}) σ^{k} {(1 - σ)}^{s - k} = σ^{- 1}$ .
The growth law $L \sim N \ln N$ agrees with (11) if the convergence of $ν$ to $2 σ$ is logarithmically slow: $2 σ - ν (N) \sim {(\ln N)}^{- 1}$ .
P. L. Krapivsky and S. Redner, Phys. Rev. E 71, 036118 (2005).
C. von Mering et al., Nature (London) 417, 399 (2002).
I. Ispolatov, P. L. Krapivsky, I. Mazo, and A. Yuryev, q-bio.MN/0502005.

Physical Review E

Export citation

Export citation

Duplication-divergence model of protein interaction network

Abstract

Article Text

References (32)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation