Since protein-protein interactions (PPIs) are central to most biological processes,the systematic identification of all PPIs is considered as an important strategy for uncovering the inner workings of a cell^[1]. A number of experimental and computational techniques have been developed to systematically determine both the potential and the actual PPIs in several model organisms. Up to now,the information of PPI networks at the whole-genome level is available from many organisms,including Saccharomyces cerevisiae (bakes yeast)^{[2, 3, 4]},Caenorhabditis elegans (worm)^[5],Drosophila melanogaster (fruit fly)^[6],and Homo sapiens (human)^{[7, 8]}. Investigations on the topological structures of these PPI networks have revealed that they share several interesting features,e.g.,sparseness,small-world,scale-free,hierarchical modularity,and disassortativity^{[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}. In order to recapture these characteristics,various network growth models invoking preferential attachment or gene duplication and divergence have been constructed. For more details,one may refer to Ref. ^[16] and the relevant references therein.

From the viewpoint of natural selection and biological evolution,duplication and divergence are the two dominant evolutionary forces in shaping biological networks^{[17, 18]}. Duplication is the primary resource for biological network growth,while divergence is the original generating function diversity. Over the past decade,according to the principle of duplication and divergence,many network models have been proposed to reproduce topological properties of real PPI networks^[16]. Cai^[16] proposed a network model,where duplication and divergence were complemented with heterodimerization,to recapture the above-mentioned five topological properties of real PPI networks,and obtained some analysis results under certain conditions. However,the results in Ref. ^[16] only considered the evolutionary process. How to select the model parameters with real biological experimental data is not mentioned in Ref. ^[16]. Therefore,the biological meanings of the results are not clear. A problem arises naturally: whether similar results can be obtained when real biological experimental data are taken into account?

To address this problem,using the real PPI statistical data,we establish a yeast PPI network model based on duplication and divergence. The simulation results show that the topological characteristics of real PPI networks can be reproduced by our network model,including sparseness,scale-free,small-world,hierarchical modularity,and disassortativity.

In PPI networks,the physical interaction of two proteins is expressed as two nodes connected by an edge. In the perspective of networks,duplication means that a new node,which has the same neighbors as the original node,is created. Naturally,the new node inherits all properties of the original node that is duplicated.

In the subsequent evolution,divergence illustrates the loss or addition of the functions of proteins. It can be represented as deleting or adding edges in the PPI networks. Deleting edges means that the divergent node loses links to its neighbors,while adding edges means that the divergent node links to the non-neighbor nodes. Specially,if edges are added between the new nodes and the original ones,the process is called heterodimerization^{[15, 16]}. In the present model,due to the unique role of heterodimerization played in biology,we consider it as an independent process,separated by the added edges.

Although a new generated protein has the same properties as the original protein,the interactions among the proteins may be lost due to the mutations or mistranslations and the omission errors in the process of gene translations^[16]. If the new generated protein has certain contribution to the biological function,it will be preserved in the evolutionary processes. Otherwise,it will become an isolated protein (isolated node) and will be removed from the network^[16].

Based on the results in Refs. ^{[15, 18, 19, 20, 21, 22]},the processes and the statistical data of the yeast PPI networks can be summarized as follows:

(i) The yeast PPI network has about 4 000 proteins. The average degree ‹k› of the nodes is about 3.74,and the degree distribution is scale-free. The average cluster correlation ‹c› is about 0.066^[15].

(ii) The duplication rate of every protein is on the order of magnitude of 10−2 per Ma (a million year). Because as many as 90% of gene duplicates are likely to eventually get lost after duplication,the effective duplication rate is about 10−3 per Ma^{[19, 20, 21, 22]}.

(iii) The rate of adding edges in every yeast duplicate protein pair is on the order of magnitude of 10−3^[20]. Although it is not easy to get the deleting-edge rate from the biological experiments,a balance between the adding edges and the deleting edges must exist because of the relative stability of the average degree of the network.

(iv) There are three different preference mechanisms in duplication and divergence. In duplication,the rule of small-preference duplication of a node means that the probability of a node chosen to duplicate is inversely proportional to its degree^{[18, 19]}. Because the nodes of the high degree (hubs) tend to be conservative,the probability of its duplication is very small. In divergence,the preference rule of the addition edges means that the larger the sum of degrees of the node pairs is,the bigger the probability of the addition edges is. The preference rule of deletion edges means that the smaller the sum of the reciprocal of the degrees of the node pair is,the larger the probability of deletion edges is.

(v) The duplicate protein is more likely to link to the original one,i.e.,the rate of heterodimerization is larger than that of non-heterodimerization^[15].

According to the above statistical data of yeast PPI networks,we present the following network evolution model:

(I) In view of (i),we start from a randomly connected network with 100 nodes,whose average degree ‹k› is close to 3.88.

(II) According to (ii) and (iv),we set one Ma as the time step. In one Ma,every node is duplicated with the probability proportional to the reciprocal of its degree. The duplication of the whole network keeps a rate of 10−3 per Ma. If a node is duplicated,we carry out the next steps. If not,we will not consider the next one until all nodes in the network have been considered in a time step.

(III) Based on (iii) and (iv),we delete the links of the new duplicate nodes. It is assumed that every edge is deleted with the probability inversely proportional to the reciprocal of the sum of degrees of the node pair.

(IV) Similarly,according to (iii) and (iv),we add edges to the new duplicate nodes. Considering all probable addition between the duplicate and the non-neighbor node (except the original one),we add edges with the probability proportional to the sum of degrees of the node pair. We assume that the addition-edges probability is equal to the deletion-edge probability. The average rate of deleting is on the order-of-magnitude of 10−3.

(V) The probability of the new duplication that heterodimerizates with the original one is denoted by p.

(VI) After the above steps,if a node is isolated from the network,we delete it.

(VII) Repeat the above six steps until the size of the PPI networks increases to 4 000.

Using the above-established network model,we perform numerical simulations. All the data are averaged over 100 independent runs. In the simulations,the parameters p and q are chosen according to the privilege that the sum of the two parameters is equal to the addition-edge rate in the simulations.

Table 1 lists the values of ‹k› and ‹c› with different values of p and q,which matches to the real data well. The results show that the simulation error is comparable with the data of the real yeast network

Table 1. Values of ‹k› and ‹c› of PPI networks

Table options

Figure 1 presents the degree distribution lines under different p and q. It is evident that they are scale-free and their exponents are between −2.3 and −2.0,consistent with the real number which are between −2 and −3. The result shows that the network is scale-free.

Fig. 1. Degree distribution P (k) (log-log scale) for different p and q

Figure options

Many biological networks display the property of hierarchical modularity^[12]. Usually,C_i is used to measure the local cohesiveness of the network in the neighborhood of the node. It is defined by

C(k) is the dependence of the average cluster coefficient C of the nodes with the same degree k. It is an essential indicator to quantify the hierarchical modularity structure of a network. C(k) approximates k−Θ when Θ approximates −1,suggesting a hierarchical structure of the network^[12]. In the present model,C(k) is consistent with the real biological observation shown in Fig. 2.

Fig. 2. Cluster degree distribution C(k) (log-log scale) for different p and q

Figure options

We analyze the degree-degree correlation of the network,which represents the connection way of the nodes in the network. If the nodes with a high degree tend to link with the nodes with a high degree,the network is assortative; if the nodes with a high degree tend to link with the low-degree nodes,we call it disassortative. Practically,we calculate the person correlation coefficient to describe this property,which is defined as follows^[23]:

Click Browse formula

Table 2. Values of D_DC for different p and q

Table options

A PPI network model is constructed based on the principle of duplication and divergence with the real yeast PPI network experimental data. This model includes five processes,i.e., duplication,edge deletion,edge addition,heterodimerization,and removal of isolated nodes. Different preference rules are discussed with the parameters obtained from the real experimental or statistic data. The numerical simulation results show that the degree distribution,the average degree,the average cluster correlation,the cluster coefficient correlation,and the degree-degree correlation of the constructed network model are all well consistent with those of real PPI networks. It is believed that the constructed PPI network model can provide insights into the mechanism underlying the evolution of PPI networks.