{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T17:19:19Z","timestamp":1783703959006,"version":"3.55.0"},"reference-count":53,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1937,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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\u2013protein 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\u2013divergence (DD) model, and models which do not copy neighbors, with the Barab\u00e1si\u2013Albert (BA) preferential attachment model as a leading example.<\/jats:p>\n               <jats:p>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 \u22654 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\u00efve unmodified DD model can capture a key aspect of PPI networks.<\/jats:p>\n               <jats:p>Contact: \u00a0regevs01@cs.huji.ac.il; michall@cc.huji.ac.il; nati@cs.huji.ac.il<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr201","type":"journal-article","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T23:32:32Z","timestamp":1308353552000},"page":"i142-i148","source":"Crossref","is-referenced-by-count":26,"title":["Generative probabilistic models for protein\u2013protein interaction networks\u2014the biclique perspective"],"prefix":"10.1093","volume":"27","author":[{"given":"Regev","family":"Schweiger","sequence":"first","affiliation":[{"name":"1 School of Computer Science and Engineering, 2Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and 3The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Linial","sequence":"additional","affiliation":[{"name":"1 School of Computer Science and Engineering, 2Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and 3The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel"},{"name":"1 School of Computer Science and Engineering, 2Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and 3The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Linial","sequence":"additional","affiliation":[{"name":"1 School of Computer Science and Engineering, 2Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and 3The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel"},{"name":"1 School of Computer Science and Engineering, 2Department of Biological Chemistry, The Alexander Silberman Institute of Life Sciences and 3The Sudarsky Center for Computational Biology, The Hebrew University, Jerusalem, 91904 Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2011,6,14]]},"reference":[{"key":"2023012512023217200_B1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert","year":"2002","journal-title":"Rev. Modern Phys."},{"key":"2023012512023217200_B2","doi-asserted-by":"crossref","first-page":"i241","DOI":"10.1093\/bioinformatics\/btn163","article-title":"Biomolecular network motif counting and discovery by color coding","volume":"24","author":"Alon","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512023217200_B3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene Ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023012512023217200_B4","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1038\/nbt1002-991","article-title":"Analyzing yeast protein\u2013protein interaction data obtained from different sources","volume":"20","author":"Bader","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023012512023217200_B5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2023012512023217200_B6","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.tcs.2006.08.045","article-title":"The degree distribution of the generalized duplication model","volume":"369","author":"Bebek","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2023012512023217200_B7","article-title":"Mathematical results on scale-free random graphs","volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","author":"Bollob\u00e1s","year":"2005"},{"key":"2023012512023217200_B8","doi-asserted-by":"crossref","first-page":"2443","DOI":"10.1093\/nar\/gkg340","article-title":"Topological structure analysis of the protein-protein interaction network in budding yeast","volume":"31","author":"Bu","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012512023217200_B9","first-page":"178","article-title":"Dense graphlet statistics of protein interaction and random networks","volume":"14","author":"Colak","year":"2009","journal-title":"14th Pac. Symp. Biocomput."},{"key":"2023012512023217200_B10","doi-asserted-by":"crossref","first-page":"6112","DOI":"10.1073\/pnas.0606779104","article-title":"Emergence of tempered preferential attachment from optimization","volume":"104","author":"D'Souza","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023217200_B11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1073\/pnas.0509715102","article-title":"A simple physical model for scaling in protein\u2013protein interaction networks","volume":"103","author":"Deeds","year":"2006","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023217200_B12","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1080\/00018730110112519","article-title":"Evolution of networks","volume":"51","author":"Dorogovtsev","year":"2002","journal-title":"Adv. Phys."},{"key":"2023012512023217200_B13","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs, I","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publicationes Mathematicae (Debrecen)"},{"key":"2023012512023217200_B14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1038\/ng1747","article-title":"Analysis of the human protein interactome and comparison with yeast, worm and fly interaction datasets","volume":"38","author":"Gandhi","year":"2006","journal-title":"Nat. Genet."},{"key":"2023012512023217200_B15","doi-asserted-by":"crossref","first-page":"4241","DOI":"10.1091\/mbc.11.12.4241","article-title":"Genomic expression programs in the response of yeast cells to environmental changes","volume":"11","author":"Gasch","year":"2000","journal-title":"Mol. Biol. Cell"},{"key":"2023012512023217200_B16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1038\/415141a","article-title":"Functional organization of the yeast proteome by systematic analysis of protein complexes","volume":"415","author":"Gavin","year":"2002","journal-title":"Nature"},{"key":"2023012512023217200_B17","doi-asserted-by":"crossref","first-page":"D436","DOI":"10.1093\/nar\/gkj003","article-title":"MPact: the MIPS protein interaction resource on yeast","volume":"34","author":"Guldener","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012512023217200_B18","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","article-title":"Evidence for dynamically organized modularity in the yeast protein\u2013protein interaction network","volume":"430","author":"Han","year":"2004","journal-title":"Nature"},{"key":"2023012512023217200_B19","doi-asserted-by":"crossref","first-page":"e118","DOI":"10.1371\/journal.pcbi.0030118","article-title":"Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution","volume":"3","author":"Hormozdiari","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023012512023217200_B20","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1038\/nprot.2008.211","article-title":"Systematic and integrative analysis of large gene lists using DAVID bioinformatics resources","volume":"4","author":"Huang da","year":"2009","journal-title":"Nat. Protoc."},{"key":"2023012512023217200_B21","doi-asserted-by":"crossref","first-page":"4569","DOI":"10.1073\/pnas.061034498","article-title":"A comprehensive two-hybrid analysis to explore the yeast protein interactome","volume":"98","author":"Ito","year":"2001","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023217200_B22","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1038\/ng0501-21","article-title":"A literature network of human genes for high-throughput analysis of gene expression","volume":"28","author":"Jenssen","year":"2001","journal-title":"Nat. Genet."},{"key":"2023012512023217200_B23","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1089\/cmb.2006.13.810","article-title":"How scale-free are biological networks","volume":"13","author":"Khanin","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012512023217200_B24","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in the yeast Saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023012512023217200_B25","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1146\/annurev.physiol.67.040403.103635","article-title":"Molecular and evolutionary basis of the cellular stress response","volume":"67","author":"Kultz","year":"2005","journal-title":"Annu. Rev. Physiol."},{"key":"2023012512023217200_B26","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1109\/SFCS.2000.892065","article-title":"Stochastic models for the Web graph","author":"Kumar","year":"2000","journal-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science"},{"key":"2023012512023217200_B27","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1093\/bioinformatics\/btl020","article-title":"Discovering motif pairs at interaction sites from protein sequences on a proteome-wide scale","volume":"22","author":"Li","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012512023217200_B28","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.1109\/TKDE.2007.190660","article-title":"Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: a one-to-one correspondence and mining algorithms","volume":"19","author":"Li","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2023012512023217200_B29","doi-asserted-by":"crossref","first-page":"1482","DOI":"10.1039\/b908681a","article-title":"The powerful law of the power law and other myths in network biology","volume":"5","author":"Lima-Mendez","year":"2009","journal-title":"Mol. Biosyst."},{"key":"2023012512023217200_B30","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1016\/j.jctb.2006.05.002","article-title":"Limits of dense graph sequences","volume":"96","author":"Lov\u00e1sz","year":"2006","journal-title":"J. Comb. Theory Ser. B"},{"key":"2023012512023217200_B31","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1186\/1471-2105-5-181","article-title":"Discriminative topological features reveal biological network mechanisms","volume":"5","author":"Middendorf","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023012512023217200_B32","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1080\/15427951.2004.10129088","article-title":"A brief history of generative models for power law and lognormal distributions","volume":"1","author":"Mitzenmacher","year":"2004","journal-title":"Internet Math."},{"key":"2023012512023217200_B33","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman","year":"2003","journal-title":"SIAM Rev."},{"key":"2023012512023217200_B34","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-86659-3","volume-title":"Evolution by Gene Duplication.","author":"Ohno","year":"1970"},{"key":"2023012512023217200_B35","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0022-5193(03)00028-6","article-title":"Evolving protein interaction networks through gene duplication","volume":"222","author":"Pastor-Satorras","year":"2003","journal-title":"J. Theor. Biol."},{"key":"2023012512023217200_B36","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","article-title":"Modeling interactome: scale-free or geometric","volume":"20","author":"Pr\u017eulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012512023217200_B37","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1038\/35051615","article-title":"The protein-protein interaction map of Helicobacter pylori","volume":"409","author":"Rain","year":"2001","journal-title":"Nature"},{"key":"2023012512023217200_B38","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/jbiol36","article-title":"Comprehensive curation and analysis of global interaction networks in Saccharomyces cerevisiae","volume":"5","author":"Reguly","year":"2006","journal-title":"J. Biol."},{"key":"2023012512023217200_B39","doi-asserted-by":"crossref","first-page":"5140","DOI":"10.1016\/j.febslet.2005.08.024","article-title":"Some protein interaction data do not exhibit power law statistics","volume":"579","author":"Reiko","year":"2005","journal-title":"FEBS Lett."},{"key":"2023012512023217200_B40","doi-asserted-by":"crossref","first-page":"D449","DOI":"10.1093\/nar\/gkh086","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012512023217200_B41","doi-asserted-by":"crossref","first-page":"10756","DOI":"10.1074\/jbc.M309909200","article-title":"A novel proteomic screen for peptide-protein interactions","volume":"279","author":"Schulze","year":"2004","journal-title":"J. Biol. Chem."},{"key":"2023012512023217200_B42","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023012512023217200_B43","doi-asserted-by":"crossref","first-page":"D535","DOI":"10.1093\/nar\/gkj109","article-title":"BioGRID: a general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012512023217200_B44","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/11599128_5","article-title":"Statistical model selection methods applied to biological networks","volume-title":"Transactions on Computational Systems Biology 3.","author":"Stumpf","year":"2005"},{"key":"2023012512023217200_B45","doi-asserted-by":"crossref","first-page":"6959","DOI":"10.1073\/pnas.0708078105","article-title":"Estimating the size of the human interactome","volume":"105","author":"Stumpf","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023217200_B46","doi-asserted-by":"crossref","first-page":"4221","DOI":"10.1073\/pnas.0501179102","article-title":"Subnets of scale-free networks are not scale free: the sampling properties of networks","volume":"102","author":"Stumpf","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023217200_B47","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/35001009","article-title":"A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae","volume":"403","author":"Uetz","year":"2000","journal-title":"Nature"},{"key":"2023012512023217200_B48","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1038\/msb4100144","article-title":"Pathway redundancy and protein essentiality revealed in the Saccharomyces cerevisiae interaction networks","volume":"3","author":"Ulitsky","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023012512023217200_B49","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.copbio.2008.06.001","article-title":"High confidence determination of specific protein-protein interactions using quantitative mass spectrometry","volume":"19","author":"Vermeulen","year":"2008","journal-title":"Curr. Opin. Biotechnol."},{"key":"2023012512023217200_B50","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein-protein interactions","volume":"417","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023012512023217200_B51","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/S0958-1669(00)00224-X","article-title":"Protein interaction databases","volume":"12","author":"Xenarios","year":"2001","journal-title":"Curr. Opin. Biotechnol."},{"key":"2023012512023217200_B52","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1126\/science.1158684","article-title":"High-quality binary protein interaction map of the yeast interactome network","volume":"322","author":"Yu","year":"2008","journal-title":"Science"},{"key":"2023012512023217200_B53","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1126\/science.1158684","article-title":"High-quality binary protein interaction map of the yeast interactome network","volume":"322","author":"Yu","year":"2008","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i142\/48870021\/bioinformatics_27_13_i142.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i142\/48870021\/bioinformatics_27_13_i142.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T14:22:10Z","timestamp":1674656530000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/13\/i142\/176912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,14]]},"references-count":53,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2011,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr201","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,7,1]]},"published":{"date-parts":[[2011,6,14]]}}}