University of Waterloo
200 University Ave W, Waterloo, ON
N2L 3G1
Phone: (519) 888-4567
Staff and Faculty Directory
Contact the Department of Electrical and Computer Engineering
Zheng Ma
A Study of Random Duplication Graphs and Degree Distribution Pattern of Protein-Protein Interaction Networks
Liang-Liang Xie
The motivation of this study is to explain the degree distribution pattern of protein-protein interaction networks. Since the degree distribution pattern of protein-protein interaction networks arises through a long-time evolutionary process of gene duplication, we introduce the model of random duplication graph to depict protein-protein networks mathematically. Specifically, we are interested in the degree distribution function of random duplication graphs, and we intend to derive the degree distribution function of protein-protein interaction networks by modeling protein-protein interaction networks as a special case of random duplication graphs.
The random duplication graph model mimics the behavior of gene duplication. In a random duplication graph, one vertex is chosen uniformly at random to duplicate at every timestep t, and all the edges of the original vertex are preserved by the new vertex. We derive the expected degree distribution function of the model from the probability master function. Furthermore, we learned from the Erdös-Rényi random graph model that the convergence of degree distribution function is difficult to tangle in a single random duplication graph. In consequences, we define the n-fold of random duplication graphs, a combination of n independent random duplication graphs, under which we are able to prove that the degree distribution function converges.
Furthermore, we model the protein-protein interaction networks as a special case of random duplication graph with sparse initial graph, and the degree distribution function of protein-protein interaction networks is derived. We compare this degree distribution function with experimental data, and show that it can fit the data adequately. Our model gives a theoretical analysis of the self-organization process of protein-protein interaction networks. Moreover, we have shown that it is the self-organization process that leads to the unique degree distribution pattern in protein-protein interaction networks, in which the degree distribution function is monotonically decreasing, the majority of proteins are sparsely connected, while highly-connected proteins also exist. We can make a further prediction based on our analysis—as the self-organization process continues, more and more high-degree proteins will be produced.
University of Waterloo
200 University Ave W, Waterloo, ON
N2L 3G1
Phone: (519) 888-4567
Staff and Faculty Directory
Contact the Department of Electrical and Computer Engineering
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.