{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:50:05Z","timestamp":1783036205137,"version":"3.54.6"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Algorithmic and modeling advances in the area of protein\u2013protein interaction (PPI) network analysis could contribute to the understanding of biological processes. Local structure of networks can be measured by the frequency distribution of graphlets, small connected non-isomorphic induced subgraphs. This measure of local structure has been used to show that high-confidence PPI networks have local structure of geometric random graphs. Finding graphlets exhaustively in a large network is computationally intensive. More complete PPI networks, as well as PPI networks of higher organisms, will thus require efficient heuristic approaches.<\/jats:p>\n               <jats:p>Results: We propose two efficient and scalable heuristics for finding graphlets in high-confidence PPI networks. We show that both PPI and their model geometric random networks, have defined boundaries that are sparser than the \u2018inner parts\u2019 of the networks. In addition, these networks exhibit \u2018uniformity\u2019 of local structure inside the networks. Our first heuristic exploits these two structural properties of PPI and geometric random networks to find good estimates of graphlet frequency distributions in these networks up to 690 times faster than the exhaustive searches. Our second heuristic is a variant of a more standard sampling technique and it produces accurate approximate results up to 377 times faster than the exhaustive searches. We indicate how the combination of these approaches may result in an even better heuristic.<\/jats:p>\n               <jats:p>Availability: Supplementary information is available at Software implementing the algorithms is available at<\/jats:p>\n               <jats:p>Contact: \u00a0juris@cs.toronto.edu; natasha@igor.ics.uci.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl030","type":"journal-article","created":{"date-parts":[[2006,2,2]],"date-time":"2006-02-02T01:24:44Z","timestamp":1138843484000},"page":"974-980","source":"Crossref","is-referenced-by-count":100,"title":["Efficient estimation of graphlet frequency distributions in protein\u2013protein interaction networks"],"prefix":"10.1093","volume":"22","author":[{"given":"N.","family":"Pr\u017eulj","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Toronto 1 \u00a0 1 \u00a0 \u00a0 Toronto M5S 3G4, Canada"},{"name":"Department of Computer Science, UC Irvine 3 \u00a0 3 \u00a0 \u00a0 Irvine, CA 92697-3435, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D. G.","family":"Corneil","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto 1 \u00a0 1 \u00a0 \u00a0 Toronto M5S 3G4, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"I.","family":"Jurisica","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto 1 \u00a0 1 \u00a0 \u00a0 Toronto M5S 3G4, Canada"},{"name":"Ontario Cancer Institute, Division of Signaling Biology 2 \u00a0 2 \u00a0 \u00a0 Toronto M5G 1L7, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2006,2,1]]},"reference":[{"key":"2023012409212703700_b1","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1126\/science.1099334","article-title":"Comment on \u201cNetwork motifs: simple building blocks of complex networks\u201d and \u201cSuperfamilies of evolved and designed networks\u201d","volume":"305","author":"Artzy-Randrup","year":"2004","journal-title":"Science"},{"key":"2023012409212703700_b2","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/BF02672069","article-title":"Nuclear DNA content of some important plant species","volume":"9","author":"Arumuganathan","year":"1991","journal-title":"Plant Mol. Biol. Rep."},{"key":"2023012409212703700_b3","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":"2023012409212703700_b4","first-page":"364","article-title":"Estimating the number of species: a review","volume":"88","author":"Bunge","year":"1993","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012409212703700_b5","first-page":"436","article-title":"Random sampling for histogram construction: how much is enough?","author":"Chaudhuri","year":"1998"},{"key":"2023012409212703700_b6","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.71.016106","article-title":"Spectral analysis and the dynamic response of complex networks","volume-title":"Phys. Rev. E. Stat. Nonlin. Soft Matter Phys.","author":"de Aguiar","year":"2005"},{"key":"2023012409212703700_b7","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/S0097539793247634","article-title":"A fast approimation algorithm for computing the frequencies of subgraphs in a given graph","volume":"24","author":"Duke","year":"1995","journal-title":"SIAM J. Comput."},{"key":"2023012409212703700_b8","first-page":"336","article-title":"Approximately counting Hamilton cycles in dense graphs","author":"Dyer","year":"1994"},{"key":"2023012409212703700_b9","first-page":"290","article-title":"On random graphs","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publ. Math."},{"key":"2023012409212703700_b10","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":"2023012409212703700_b11","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic counting algorithms for data base applications","volume":"31","author":"Flajolet","year":"1985","journal-title":"Comput. Sys. Sci."},{"key":"2023012409212703700_b12","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2023012409212703700_b13","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":"2023012409212703700_b14","first-page":"541","article-title":"Distinct sampling for highly-accurate answers to distinct values queries and event reports","author":"Gibbons","year":"2001"},{"key":"2023012409212703700_b15","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1126\/science.1090289","article-title":"A protein interaction map of Drosophila melanogaster","volume":"302","author":"Giot","year":"2003","journal-title":"Science"},{"key":"2023012409212703700_b16","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1038\/nbt1116","article-title":"Effects of sampling on topology predictions of protein-protein interaction networks","volume":"23","author":"Han","year":"2005","journal-title":"Nat. Biotechnol."},{"key":"2023012409212703700_b17","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1038\/415180a","article-title":"Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry","volume":"415","author":"Ho","year":"2002","journal-title":"Nature"},{"key":"2023012409212703700_b18","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1038\/nature03895","article-title":"The map-based sequence of the rice genome","volume":"436","author":"IRGSP International Rice Genome Sequencing Project","year":"2005","journal-title":"Nature"},{"key":"2023012409212703700_b19","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":"2023012409212703700_b20","article-title":"Coarse graining and self-dissimilarity of complex networks","author":"Itzkovitz","year":"2005","journal-title":"Phys. Rev."},{"key":"2023012409212703700_b21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating: Algorithms and Complexity","author":"Jerrum","year":"2003"},{"key":"2023012409212703700_b22","doi-asserted-by":"crossref","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","article-title":"Series: Lecture Notes in Mathematics, ETH Zurich. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs","volume":"20","author":"Kashtan","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012409212703700_b23","first-page":"11060","article-title":"Revisiting \u201cscale-free\u201d networks","volume":"27","author":"Keller","year":"2005","journal-title":"BioEssays"},{"key":"2023012409212703700_b24","doi-asserted-by":"crossref","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","article-title":"Protein complex prediction via cost-based clustering","volume":"20","author":"King","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012409212703700_b25","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1038\/nbt921","article-title":"Unraveling protein interaction networks with near-optimal efficiency","volume":"22","author":"Lappe","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"2023012409212703700_b26","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1126\/science.1091403","article-title":"A map of the interactome network of the metazoan caenorhabditis elegans","volume":"303","author":"Li","year":"2004","journal-title":"Science"},{"key":"2023012409212703700_b27","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":"2023012409212703700_b28","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF00140664","article-title":"Random sampling from databases\u2014a survey","volume":"5","author":"Olkon","year":"1995","journal-title":"Stat. Comput."},{"key":"2023012409212703700_b29","unstructured":"Pr\u017eulj\n              N.\n            \n          \n          Analyzing large biological networks: protein\u2013protein interactions example\n          2005\n          Ph. D. thesis. University of Toronto, Canada"},{"key":"2023012409212703700_b30","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":"2023012409212703700_b31","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","article-title":"Functional topology in a network of protein interactions","volume":"20","author":"Pr\u017eulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012409212703700_b32","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1126\/science.1073374","article-title":"Hierarchical organization of modularity in metabolic networks","volume":"297","author":"Ravasz","year":"2002","journal-title":"Science"},{"key":"2023012409212703700_b33","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":"2023012409212703700_b34","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1038\/nature03248","article-title":"Self-similarity of complex networks","volume":"433","author":"Song","year":"2005","journal-title":"Nature"},{"key":"2023012409212703700_b35","doi-asserted-by":"crossref","first-page":"4221","DOI":"10.1073\/pnas.0501179102","article-title":"Subnets of scale-free networks are not scale-free: sampling properties of networks","volume":"102","author":"Stumpf","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012409212703700_b36","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.94.168101","article-title":"Scale-rich metabolic networks","volume":"94","author":"Tanaka","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"2023012409212703700_b37","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":"Tanaka","year":"2005","journal-title":"FEBS lett."},{"key":"2023012409212703700_b38","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/35001009","article-title":"A comprehensive analysis of protein\u2013protein interactions in Saccharomyces cerevisiae","volume":"403","author":"Uetz","year":"2000","journal-title":"Nature"},{"key":"2023012409212703700_b39","doi-asserted-by":"crossref","first-page":"17940","DOI":"10.1073\/pnas.0406024101","article-title":"The topological relationship between the large-scale attributes and local interaction patterns of complex networks","volume":"101","author":"Vazquez","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012409212703700_b40","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale datasets of protein\u2013protein 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\/22\/8\/974\/48841561\/bioinformatics_22_8_974.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/8\/974\/48841561\/bioinformatics_22_8_974.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T10:00:32Z","timestamp":1674554432000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/8\/974\/227107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,2,1]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2006,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl030","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,4,15]]},"published":{"date-parts":[[2006,2,1]]}}}