{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:28:47Z","timestamp":1773275327447,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2220,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: A wealth of protein\u2013protein interaction (PPI) data has recently become available. These data are organized as PPI networks and an efficient and biologically meaningful method to compare such PPI networks is needed. As a first step, we would like to compare observed networks to established network models, under the aspect of small subgraph counts, as these are conjectured to relate to functional modules in the PPI network. We employ the software tool GraphCrunch with the Graphlet Degree Distribution Agreement (GDDA) score to examine the use of such counts for network comparison.<\/jats:p>\n               <jats:p>Results: Our results show that the GDDA score has a pronounced dependency on the number of edges and vertices of the networks being considered. This should be taken into account when testing the fit of models. We provide a method for assessing the statistical significance of the fit between random graph models and biological networks based on non-parametric tests. Using this method we examine the fit of Erd\u00f6s\u2013R\u00e9nyi (ER), ER with fixed degree distribution and geometric (3D) models to PPI networks. Under these rigorous tests none of these models fit to the PPI networks. The GDDA score is not stable in the region of graph density relevant to current PPI networks. We hypothesize that this score instability is due to the networks under consideration having a graph density in the threshold region for the appearance of small subgraphs. This is true for both geometric (3D) and ER random graph models. Such threshold behaviour may be linked to the robustness and efficiency properties of the PPI networks.<\/jats:p>\n               <jats:p>Contact: \u00a0tiago@stats.ox.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq386","type":"journal-article","created":{"date-parts":[[2010,9,7]],"date-time":"2010-09-07T17:41:46Z","timestamp":1283881306000},"page":"i611-i617","source":"Crossref","is-referenced-by-count":28,"title":["How threshold behaviour affects the use of subgraphs for network comparison"],"prefix":"10.1093","volume":"26","author":[{"given":"Tiago","family":"Rito","sequence":"first","affiliation":[{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"},{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zi","family":"Wang","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charlotte M.","family":"Deane","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"},{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gesine","family":"Reinert","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"},{"name":"1 Department of Statistics, University of Oxford, OX1 3TG and 2OCISB\/DTC Systems Biology, Department of Biochemistry, South Parks Road, OX1 3QU, UK&rcub;"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,9,4]]},"reference":[{"key":"2023012508263073100_B1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0959-440X(03)00031-9","article-title":"Biological networks","volume":"13","author":"Alm","year":"2003","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012508263073100_B2","doi-asserted-by":"crossref","first-page":"1367","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":"2023012508263073100_B3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs.","author":"Bollob\u00e1s,B.","year":"2001"},{"key":"2023012508263073100_B4","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1093\/bfgp\/eln015","article-title":"A review on models and algorithms for motif discovery in protein-protein interaction networks","volume":"7","author":"Ciriello","year":"2008","journal-title":"Brief. Funct. Genomics Proteomics"},{"key":"2023012508263073100_B5","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1080\/00018730601170527","article-title":"Characterization of complex networks: A survey of measurements","volume":"56","author":"Costa","year":"2007","journal-title":"Adv. Phys."},{"key":"2023012508263073100_B6","doi-asserted-by":"crossref","first-page":"16121","DOI":"10.1103\/PhysRevE.66.016121","article-title":"Random geometric graphs","volume":"66","author":"Dall","year":"2002","journal-title":"Phys. Rev. E"},{"key":"2023012508263073100_B7","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s11222-007-9046-7","article-title":"A mixture model for random graphs","volume":"18","author":"Daudin","year":"2008","journal-title":"Stat. Comput."},{"key":"2023012508263073100_B8","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"2023012508263073100_B9","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/978-3-540-71681-5_7","article-title":"Network motif discovery using subgraph enumeration and symmetry-breaking","volume":"4453","author":"Grochow","year":"2007","journal-title":"Lect. Notes Comput. Sci."},{"issue":"Suppl. 6761","key":"2023012508263073100_B10","doi-asserted-by":"crossref","first-page":"C47","DOI":"10.1038\/35011540","article-title":"From molecular to modular cell biology","volume":"402","author":"Hartwell","year":"1999","journal-title":"Nature"},{"key":"2023012508263073100_B11","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":"2023012508263073100_B12","first-page":"1","article-title":"Network motifs: structure does not determine function","volume":"7","author":"Ingram","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012508263073100_B13","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1073\/pnas.97.3.1143","article-title":"Toward a protein\u2013protein interaction map of the budding yeast: a comprehensive system to examine two-hybrid interactions in all possible combinations between the yeast proteins","volume":"97","author":"Ito","year":"2000","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508263073100_B14","doi-asserted-by":"crossref","first-page":"4166","DOI":"10.1109\/IEMBS.2009.5333938","article-title":"Structure of brain functional networks","volume-title":"Annual International Conference of the IEEE Engineering in Medicine and Biology Society","author":"Kuchaiev","year":"2009"},{"key":"2023012508263073100_B15","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1186\/1471-2105-9-70","article-title":"Graphcrunch: a tool for large network analyses","volume":"9","author":"Milenkovic","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012508263073100_B16","doi-asserted-by":"crossref","first-page":"e5967","DOI":"10.1371\/journal.pone.0005967","article-title":"Optimized null model for protein structure networks","volume":"4","author":"Milenkovic","year":"2009","journal-title":"PLoS ONE"},{"key":"2023012508263073100_B17","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2023012508263073100_B18","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random Geometric Graphs.","author":"Penrose","year":"2003"},{"key":"2023012508263073100_B19","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1098\/rsif.2006.0147","article-title":"Modelling protein\u2013protein interaction networks via a stickiness index","volume":"3","author":"Pr\u017eulj","year":"2006","journal-title":"J. R. Soc. Interface"},{"key":"2023012508263073100_B20","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","article-title":"Modeling interactome: scale-free or geometric?","volume":"20","author":"Przulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012508263073100_B21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Przulj","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012508263073100_B22","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1093\/bioinformatics\/btq091","article-title":"Biological network comparison using graphlet degree distribution","volume":"26","author":"Przulj","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012508263073100_B23","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1038\/nature04209","article-title":"Towards a proteome-scale map of the human protein\u2013protein interaction network","volume":"437","author":"Rual","year":"2005","journal-title":"Nature"},{"key":"2023012508263073100_B24","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechnol."},{"key":"2023012508263073100_B25","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1038\/ng881","article-title":"Network motifs in the transcriptional regulation network of Escherichia coli","volume":"31","author":"Shen-Orr","year":"2002","journal-title":"Nat. Genet."},{"key":"2023012508263073100_B26","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1016\/j.cell.2005.08.029","article-title":"A human protein-protein interaction network: a resource for annotating the proteome","volume":"122","author":"Stelzl","year":"2005","journal-title":"Cell"},{"key":"2023012508263073100_B27","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":"2023012508263073100_B28","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/i611\/48855846\/bioinformatics_26_18_i611.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/i611\/48855846\/bioinformatics_26_18_i611.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:26:58Z","timestamp":1674635218000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/18\/i611\/206361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,4]]},"references-count":28,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2010,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq386","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,9,15]]},"published":{"date-parts":[[2010,9,4]]}}}