{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T03:16:46Z","timestamp":1787887006700,"version":"build-2784847793"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Finding a good network null model for protein\u2013protein interaction (PPI) networks is a fundamental issue. Such a model would provide insights into the interplay between network structure and biological function as well as into evolution. Also, network (graph) models are used to guide biological experiments and discover new biological features. It has been proposed that geometric random graphs are a good model for PPI networks. In a geometric random graph, nodes correspond to uniformly randomly distributed points in a metric space and edges (links) exist between pairs of nodes for which the corresponding points in the metric space are close enough according to some distance norm. Computational experiments have revealed close matches between key topological properties of PPI networks and geometric random graph models. In this work, we push the comparison further by exploiting the fact that the geometric property can be tested for directly. To this end, we develop an algorithm that takes PPI interaction data and embeds proteins into a low-dimensional Euclidean space, under the premise that connectivity information corresponds to Euclidean proximity, as in geometric-random graphs. We judge the sensitivity and specificity of the fit by computing the area under the Receiver Operator Characteristic (ROC) curve. The network embedding algorithm is based on multi-dimensional scaling, with the square root of the path length in a network playing the role of the Euclidean distance in the Euclidean space. The algorithm exploits sparsity for computational efficiency, and requires only a few sparse matrix multiplications, giving a complexity of O(N2) where N is the number of proteins.<\/jats:p>\n               <jats:p>Results: The algorithm has been verified in the sense that it successfully rediscovers the geometric structure in artificially constructed geometric networks, even when noise is added by re-wiring some links. Applying the algorithm to 19 publicly available PPI networks of various organisms indicated that: (a) geometric effects are present and (b) two-dimensional Euclidean space is generally as effective as higher dimensional Euclidean space for explaining the connectivity. Testing on a high-confidence yeast data set produced a very strong indication of geometric structure (area under the ROC curve of 0.89), with this network being essentially indistinguishable from a noisy geometric network. Overall, the results add support to the hypothesis that PPI networks have a geometric structure.<\/jats:p>\n               <jats:p>Availability: MATLAB code implementing the algorithm is available upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0natasha@ics.uci.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn079","type":"journal-article","created":{"date-parts":[[2008,3,15]],"date-time":"2008-03-15T00:45:23Z","timestamp":1205541923000},"page":"1093-1099","source":"Crossref","is-referenced-by-count":98,"title":["Fitting a geometric graph to a protein\u2013protein interaction network"],"prefix":"10.1093","volume":"24","author":[{"given":"Desmond J.","family":"Higham","sequence":"first","affiliation":[{"name":"1 Department of Mathematics, University of Strathclyde, Glasgow G1 1XH, UK, 2Department of Computer Science, UC Irvine, Irvine, CA 92697, USA and 3Faculty of Electrical Engineering, University of Belgrade, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marija","family":"Ra\u0161ajski","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics, University of Strathclyde, Glasgow G1 1XH, UK, 2Department of Computer Science, UC Irvine, Irvine, CA 92697, USA and 3Faculty of Electrical Engineering, University of Belgrade, Belgrade, Serbia"},{"name":"1 Department of Mathematics, University of Strathclyde, Glasgow G1 1XH, UK, 2Department of Computer Science, UC Irvine, Irvine, CA 92697, USA and 3Faculty of Electrical Engineering, University of Belgrade, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nata\u0161a","family":"Pr\u017eulj","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics, University of Strathclyde, Glasgow G1 1XH, UK, 2Department of Computer Science, UC Irvine, Irvine, CA 92697, USA and 3Faculty of Electrical Engineering, University of Belgrade, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2008,3,14]]},"reference":[{"key":"2023020210012433900_B1","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":"2023020210012433900_B2","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","article-title":"The asymptotic number of labeled graphs with given degree sequences","volume":"24","author":"Bender","year":"1978","journal-title":"J. Combinatorial Theory A"},{"key":"2023020210012433900_B3","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1016\/S0031-3203(96)00142-2","article-title":"The use of the area under the ROC curve in the evaluation of machine learning algorithms","volume":"30","author":"Bradley","year":"1997","journal-title":"Pattern Recogn."},{"key":"2023020210012433900_B4","volume-title":"Multidimensional Scaling","author":"Cox","year":"1994"},{"key":"2023020210012433900_B5","first-page":"290","article-title":"On random graphs","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publ. Math."},{"key":"2023020210012433900_B6","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":"2023020210012433900_B7","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":"2023020210012433900_B8","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":"2023020210012433900_B9","volume-title":"Matrix Computations","author":"Golub","year":"1996","edition":"3rd"},{"key":"2023020210012433900_B10","doi-asserted-by":"crossref","first-page":"066702","DOI":"10.1103\/PhysRevE.66.066702","article-title":"Range-dependent random graphs and their application to modeling large small-world proteome datasets","volume":"66","author":"Grindrod","year":"2002","journal-title":"Phys. Rev. E"},{"key":"2023020210012433900_B11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1586\/14789450.1.2.229","article-title":"Review of uses of network and graph theory concepts within proteomics","volume":"1","author":"Grindrod","year":"2004","journal-title":"Expert Rev. Proteomics"},{"key":"2023020210012433900_B12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0377-0427(03)00471-0","article-title":"Unravelling small world networks","volume":"158","author":"Higham","year":"2003","journal-title":"J. Comp. Appl. Math."},{"key":"2023020210012433900_B13","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":"2023020210012433900_B14","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":"2023020210012433900_B15","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1186\/1471-2105-4-48","article-title":"Trustworthiness and metrics in visualizing similarity of gene expression","volume":"4","author":"Kaski","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023020210012433900_B16","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1089\/cmb.2006.13.810","article-title":"How scale-free are gene networks?","volume":"13","author":"Khanin","year":"2006","journal-title":"J. Computat. Biol."},{"key":"2023020210012433900_B17","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":"2023020210012433900_B18","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":"2023020210012433900_B19","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1126\/science.1091403","article-title":"A map of the interactome network of the metazoan c elegans","volume":"303","author":"Li","year":"2004","journal-title":"Science"},{"key":"2023020210012433900_B20","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1093\/nar\/30.1.31","article-title":"MIPS: a database for genomes and protein sequences","volume":"30","author":"Mewes","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023020210012433900_B21","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":"2023020210012433900_B22","doi-asserted-by":"crossref","first-page":"2012","DOI":"10.1093\/bioinformatics\/btl338","article-title":"A lock-and-key model for protein\u2013protein interactions","volume":"22","author":"Morrison","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210012433900_B23","doi-asserted-by":"crossref","first-page":"1971","DOI":"10.1101\/gr.206701","article-title":"Is there a bias in proteome research?","volume":"11","author":"Mrowka","year":"2001","journal-title":"Genome Res."},{"key":"2023020210012433900_B24","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":"2023020210012433900_B25","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Geometric Random Graphs","author":"Penrose","year":"2003"},{"key":"2023020210012433900_B26","article-title":"Human protein reference database as a discovery resource for proteomics","volume":"32 Database issue","author":"Peri","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023020210012433900_B27","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210012433900_B28","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":"2023020210012433900_B29","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":"2023020210012433900_B30","doi-asserted-by":"crossref","first-page":"974","DOI":"10.1093\/bioinformatics\/btl030","article-title":"Efficient estimation of graphlet frequency distributions in protein\u2013protein interaction networks","volume":"22","author":"Pr\u017eulj","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210012433900_B31","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":"2023020210012433900_B32","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1093\/biomet\/42.3-4.425","article-title":"On a class of skew distribution functions","volume":"42","author":"Simon","year":"1955","journal-title":"Biometrika"},{"key":"2023020210012433900_B33","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1016\/j.cell.2005.08.029","article-title":"A human proteinprotein interaction network: a resource for annotating the proteome","volume":"122","author":"Stelzl","year":"2005","journal-title":"Cell"},{"key":"2023020210012433900_B34","article-title":"Relational patterns of gene expression via nonmetric multidimensional scaling analysis","author":"Taguchi","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020210012433900_B35","article-title":"Interpreting diagnostic tests","author":"Tape","year":"2000","journal-title":"University of Nebraska Medical Center"},{"key":"2023020210012433900_B36","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1042\/bst0311491","article-title":"On the structure of protein\u2013protein interaction networks","volume":"31","author":"Thomas","year":"2003","journal-title":"Biochem. Soc. Trans."},{"key":"2023020210012433900_B37","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1586\/14789450.1.1.111","article-title":"What do we learn from high-throughput protein interaction data","volume":"1","author":"Titz","year":"2004","journal-title":"Expert Rev. Proteomics"},{"key":"2023020210012433900_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":"2023020210012433900_B39","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modeling of protein interaction networks","volume":"1","author":"Vazquez","year":"2001","journal-title":"ComPlexUs"},{"key":"2023020210012433900_B40","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein\u2013protein interactions","volume":"417","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023020210012433900_B41","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"2023020210012433900_B42","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1093\/nar\/28.1.289","article-title":"DIP: the Database of Interacting Proteins","volume":"28","author":"Xenarios","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023020210012433900_B43","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0014-5793(01)03293-8","article-title":"Mint: a molecular interaction database","volume":"513","author":"Zanzoni","year":"2002","journal-title":"FEBS Letters"},{"key":"2023020210012433900_B44","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1126\/science.1123287","article-title":"Genome-wide prediction of C. elegans genetic interactions","volume":"311","author":"Zhong","year":"2006","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/8\/1093\/49046772\/bioinformatics_24_8_1093.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/8\/1093\/49046772\/bioinformatics_24_8_1093.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T11:22:50Z","timestamp":1675336970000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/8\/1093\/213389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,14]]},"references-count":44,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2008,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn079","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,4,15]]},"published":{"date-parts":[[2008,3,14]]}}}