Limits...
Generative probabilistic models for protein-protein interaction networks--the biclique perspective.

Schweiger R, Linial M, Linial N - Bioinformatics (2011)

Bottom Line: We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example.In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%.Our results, based on the biclique perspective, conclusively show that a naïve unmodified DD model can capture a key aspect of PPI networks.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Engineering, Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel. regevs01@cs.huji.ac.il

ABSTRACT

Motivation: Much of the large-scale molecular data from living cells can be represented in terms of networks. Such networks occupy a central position in cellular systems biology. In the protein-protein interaction (PPI) network, nodes represent proteins and edges represent connections between them, based on experimental evidence. As PPI networks are rich and complex, a mathematical model is sought to capture their properties and shed light on PPI evolution. The mathematical literature contains various generative models of random graphs. It is a major, still largely open question, which of these models (if any) can properly reproduce various biologically interesting networks. Here, we consider this problem where the graph at hand is the PPI network of Saccharomyces cerevisiae. We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example.

Results: The observed property of the network is the distribution of maximal bicliques in the graph. This is a novel criterion to distinguish between models in this area. It is particularly appropriate for this purpose, since it reflects the graph's growth pattern under either model. This test clearly favors the DD model. In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%. Our results, based on the biclique perspective, conclusively show that a naïve unmodified DD model can capture a key aspect of PPI networks.

Show MeSH
Seed model illustrations. (A) Random geometric model. Random points are sampled from a standardized normal distribution on Rd (here d=2). Each node corresponds to a point, and two nodes are connected in the graph if the corresponding two points are at distance smaller than ρ. (B) Inverse random geometric model. Similar to the geometric model, except two nodes are connected when the corresponding points are at distance R or above (here d=2). (C) ER model. Every edge is independently inserted at a probability p.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3117378&req=5

Figure 4: Seed model illustrations. (A) Random geometric model. Random points are sampled from a standardized normal distribution on Rd (here d=2). Each node corresponds to a point, and two nodes are connected in the graph if the corresponding two points are at distance smaller than ρ. (B) Inverse random geometric model. Similar to the geometric model, except two nodes are connected when the corresponding points are at distance R or above (here d=2). (C) ER model. Every edge is independently inserted at a probability p.

Mentions: ER model: there are m0 nodes, and each possible edge between two nodes exists uniformly at random with a probability P. See Figure 4 for a schematic representation of the seed graph models.


Generative probabilistic models for protein-protein interaction networks--the biclique perspective.

Schweiger R, Linial M, Linial N - Bioinformatics (2011)

Seed model illustrations. (A) Random geometric model. Random points are sampled from a standardized normal distribution on Rd (here d=2). Each node corresponds to a point, and two nodes are connected in the graph if the corresponding two points are at distance smaller than ρ. (B) Inverse random geometric model. Similar to the geometric model, except two nodes are connected when the corresponding points are at distance R or above (here d=2). (C) ER model. Every edge is independently inserted at a probability p.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3117378&req=5

Figure 4: Seed model illustrations. (A) Random geometric model. Random points are sampled from a standardized normal distribution on Rd (here d=2). Each node corresponds to a point, and two nodes are connected in the graph if the corresponding two points are at distance smaller than ρ. (B) Inverse random geometric model. Similar to the geometric model, except two nodes are connected when the corresponding points are at distance R or above (here d=2). (C) ER model. Every edge is independently inserted at a probability p.
Mentions: ER model: there are m0 nodes, and each possible edge between two nodes exists uniformly at random with a probability P. See Figure 4 for a schematic representation of the seed graph models.

Bottom Line: We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example.In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%.Our results, based on the biclique perspective, conclusively show that a naïve unmodified DD model can capture a key aspect of PPI networks.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Engineering, Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel. regevs01@cs.huji.ac.il

ABSTRACT

Motivation: Much of the large-scale molecular data from living cells can be represented in terms of networks. Such networks occupy a central position in cellular systems biology. In the protein-protein interaction (PPI) network, nodes represent proteins and edges represent connections between them, based on experimental evidence. As PPI networks are rich and complex, a mathematical model is sought to capture their properties and shed light on PPI evolution. The mathematical literature contains various generative models of random graphs. It is a major, still largely open question, which of these models (if any) can properly reproduce various biologically interesting networks. Here, we consider this problem where the graph at hand is the PPI network of Saccharomyces cerevisiae. We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example.

Results: The observed property of the network is the distribution of maximal bicliques in the graph. This is a novel criterion to distinguish between models in this area. It is particularly appropriate for this purpose, since it reflects the graph's growth pattern under either model. This test clearly favors the DD model. In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%. Our results, based on the biclique perspective, conclusively show that a naïve unmodified DD model can capture a key aspect of PPI networks.

Show MeSH