{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:34:52Z","timestamp":1784198092427,"version":"3.55.0"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"16","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":558,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Network comparison is a computationally intractable problem with important applications in systems biology and other domains. A key challenge is to properly quantify similarity between wiring patterns of two networks in an alignment-free fashion. Also, alignment-based methods exist that aim to identify an actual node mapping between networks and as such serve a different purpose. Various alignment-free methods that use different global network properties (e.g. degree distribution) have been proposed. Methods based on small local subgraphs called graphlets perform the best in the alignment-free network comparison task, due to high level of topological detail that graphlets can capture. Among different graphlet-based methods, Graphlet Correlation Distance (GCD) was shown to be the most accurate for comparing networks. Recently, a new graphlet-based method called NetDis was proposed, which was claimed to be superior. We argue against this, as the performance of NetDis was not properly evaluated to position it correctly among the other alignment-free methods.<\/jats:p>\n               <jats:p>Results: We evaluate the performance of available alignment-free network comparison methods, including GCD and NetDis. We do this by measuring accuracy of each method (in a systematic precision-recall framework) in terms of how well the method can group (cluster) topologically similar networks. By testing this on both synthetic and real-world networks from different domains, we show that GCD remains the most accurate, noise-tolerant and computationally efficient alignment-free method. That is, we show that NetDis does not outperform the other methods, as originally claimed, while it is also computationally more expensive. Furthermore, since NetDis is dependent on the choice of a network null model (unlike the other graphlet-based methods), we show that its performance is highly sensitive to the choice of this parameter. Finally, we find that its performance is not independent on network sizes and densities, as originally claimed.<\/jats:p>\n               <jats:p>Contact: natasha@imperial.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv170","type":"journal-article","created":{"date-parts":[[2015,3,26]],"date-time":"2015-03-26T04:39:55Z","timestamp":1427344795000},"page":"2697-2704","source":"Crossref","is-referenced-by-count":49,"title":["Proper evaluation of alignment-free network comparison methods"],"prefix":"10.1093","volume":"31","author":[{"given":"\u00d6mer Nebil","family":"Yavero\u011flu","sequence":"first","affiliation":[{"name":"1 California Institute for Telecommunications and Information Technology (Calit2), University of California, Irvine, CA 92697, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tijana","family":"Milenkovi\u0107","sequence":"additional","affiliation":[{"name":"2 Department of Computer Science and Engineering, University of Notre Dame, IN 46556, USA and"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nata\u0161a","family":"Pr\u017eulj","sequence":"additional","affiliation":[{"name":"3 Department of Computing, Imperial College London, London SW7 2AZ, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,3,24]]},"reference":[{"key":"2023020202202797600_btv170-B1","doi-asserted-by":"crossref","first-page":"i430","DOI":"10.1093\/bioinformatics\/btu447","article-title":"Alignment-free protein interaction network comparison","volume":"30","author":"Ali","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B2","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1126\/science.1099334","article-title":"Comment on\u201d network motifs: simple building blocks of complex networks\u201d and\u201d superfamilies of evolved and designed networks\u201d","volume":"305","author":"Artzy-Randrup","year":"2004","journal-title":"Science"},{"key":"2023020202202797600_btv170-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":"2023020202202797600_btv170-B4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/800157.805047","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971","journal-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM"},{"key":"2023020202202797600_btv170-B5","first-page":"343","article-title":"On the evolution of random graphs","volume":"38","author":"Erdos","year":"1961","journal-title":"Bull. Inst. Int. Stat."},{"key":"2023020202202797600_btv170-B6","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199591756.001.0001","volume-title":"The Structure of Complex Networks: Theory and Applications","author":"Estrada","year":"2011"},{"key":"2023020202202797600_btv170-B7","first-page":"99","article-title":"Global network alignment in the context of aging","author":"Faisal","year":"2014","journal-title":"Computational Biology and Bioinformatics, IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2023020202202797600_btv170-B8","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.physa.2005.02.075","article-title":"Structure and evolution of the world trade network","volume":"355","author":"Garlaschelli","year":"2005","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"2023020202202797600_btv170-B9","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1093\/bioinformatics\/bts729","article-title":"Graphlet-based measures are suitable for biological network comparison","volume":"29","author":"Hayes","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B10","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1093\/bioinformatics\/btt717","article-title":"A combinatorial approach to graphlet counting","volume":"30","author":"Ho\u010devar","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B11","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1038\/ng2012","article-title":"Genetic reconstruction of a functional transcriptional regulatory network","volume":"39","author":"Hu","year":"2007","journal-title":"Nat. Genet."},{"key":"2023020202202797600_btv170-B12","first-page":"68","article-title":"Gedevo: an evolutionary graph edit distance algorithm for biological network alignment","author":"Ibragimov","year":"2013","journal-title":"German Conference on Bioinformatics 2013 (GCB\u20192013)"},{"key":"2023020202202797600_btv170-B13","first-page":"277","article-title":"Multiple graph edit distance: simultaneous topological alignment of multiple protein-protein interaction networks with an evolutionary algorithm","author":"Ibragimov","year":"2014","journal-title":"In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation (GECCO\u20192014)"},{"key":"2023020202202797600_btv170-B14","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA."},{"key":"2023020202202797600_btv170-B15","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1126\/science.1116869","article-title":"Empirical analysis of an evolving social network","volume":"311","author":"Kossinets","year":"2006","journal-title":"Science"},{"key":"2023020202202797600_btv170-B16","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B17","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1126\/science.1075090","article-title":"Transcriptional regulatory networks in Saccharomyces cerevisiae","volume":"298","author":"Lee","year":"2002","journal-title":"Science"},{"key":"2023020202202797600_btv170-B18","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"Isorankn: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B19","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1093\/bioinformatics\/btu020","article-title":"GR-align: fast and flexible alignment of protein 3D structures using graphlet degree similarity","volume":"30","author":"Malod-Dognin","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B20","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4137\/CIN.S680","article-title":"Uncovering biological network function via graphlet degree signatures","volume":"6","author":"Milenkovi\u0107","year":"2008","journal-title":"Cancer Inform."},{"key":"2023020202202797600_btv170-B21","doi-asserted-by":"crossref","first-page":"1538","DOI":"10.1126\/science.1089167","article-title":"Superfamilies of evolved and designed networks","volume":"303","author":"Milo","year":"2004","journal-title":"Science"},{"key":"2023020202202797600_btv170-B22","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"Newman","year":"2010"},{"key":"2023020202202797600_btv170-B23","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1093\/bioinformatics\/btt202","article-title":"NETAL: a new graph-based method for global alignment of protein\u2013protein interaction networks","volume":"29","author":"Neyshabur","year":"2013","journal-title":"Bioinformatics"},{"issue":"Suppl. 2","key":"2023020202202797600_btv170-B24","doi-asserted-by":"crossref","first-page":"W423","DOI":"10.1093\/nar\/gkn282","article-title":"KEGG atlas mapping for global analysis of metabolic pathways","volume":"36","author":"Okuda","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023020202202797600_btv170-B25","doi-asserted-by":"crossref","first-page":"3105","DOI":"10.1093\/bioinformatics\/bts592","article-title":"Global network alignment using multiscale spectral signatures","volume":"28","author":"Patro","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B26","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random Geometric Graphs. Vo. 5","author":"Penrose","year":"2003"},{"key":"2023020202202797600_btv170-B27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511984570","volume-title":"Bioinformatics for Biologists","author":"Pevzner","year":"2011"},{"issue":"Suppl. 1","key":"2023020202202797600_btv170-B28","doi-asserted-by":"crossref","first-page":"D767","DOI":"10.1093\/nar\/gkn892","article-title":"Human protein reference database 2009 update","volume":"37","author":"Prasad","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023020202202797600_btv170-B29","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":"2007","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B30","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":"2023020202202797600_btv170-B31","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":"2023020202202797600_btv170-B32","first-page":"178","article-title":"Geometric evolutionary dynamics of protein interaction networks","author":"Pr\u017eulj","year":"2010","journal-title":"In: Pacific Symposium on Biocomputing, Vol. 2009"},{"key":"2023020202202797600_btv170-B33","doi-asserted-by":"crossref","first-page":"i611","DOI":"10.1093\/bioinformatics\/btq386","article-title":"How threshold behaviour affects the use of subgraphs for network comparison","volume":"26","author":"Rito","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B34","doi-asserted-by":"crossref","first-page":"2931","DOI":"10.1093\/bioinformatics\/btu409","article-title":"MAGNA: maximizing accuracy in global network alignment","volume":"30","author":"Saraph","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020202202797600_btv170-B35","doi-asserted-by":"crossref","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA."},{"key":"2023020202202797600_btv170-B36","doi-asserted-by":"crossref","first-page":"i480","DOI":"10.1093\/bioinformatics\/bts376","article-title":"Graphlet-based edge clustering reveals pathogen-interacting proteins","volume":"18","author":"Solava","year":"2012","journal-title":"Bioinformatics"},{"issue":"Suppl 1","key":"2023020202202797600_btv170-B37","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":"2023020202202797600_btv170-B38","doi-asserted-by":"crossref","first-page":"2653","DOI":"10.1098\/rsif.2012.0220","article-title":"Graph spectral analysis of protein interaction network evolution","volume":"9","author":"Thorne","year":"2012","journal-title":"J, R. Soc. Interface."},{"key":"2023020202202797600_btv170-B39","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1126\/science.1091317","article-title":"Global mapping of the yeast genetic interaction network","volume":"303","author":"Tong","year":"2004","journal-title":"Science"},{"key":"2023020202202797600_btv170-B40","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modeling of protein interaction networks","volume":"1","author":"V\u00e1zquez","year":"2002","journal-title":"Complexus"},{"key":"2023020202202797600_btv170-B41","doi-asserted-by":"crossref","first-page":"2833","DOI":"10.1016\/j.patcog.2008.03.011","article-title":"A study of graph spectra for comparing graphs and trees","volume":"41","author":"Wilson","year":"2008","journal-title":"Pattern Recognit."},{"key":"2023020202202797600_btv170-B42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/srep04547","article-title":"Revealing the hidden language of complex networks","volume":"4","author":"Yavero\u011flu","year":"2014","journal-title":"Sci. Rep."},{"key":"2023020202202797600_btv170-B43","doi-asserted-by":"crossref","first-page":"2302","DOI":"10.1093\/nar\/gki524","article-title":"Tm-align: a protein structure alignment algorithm based on the tm-score","volume":"33","author":"Zhang","year":"2005","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2697\/49034821\/bioinformatics_31_16_2697.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2697\/49034821\/bioinformatics_31_16_2697.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T03:44:47Z","timestamp":1675309487000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/16\/2697\/320753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,24]]},"references-count":43,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2015,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv170","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,8,15]]},"published":{"date-parts":[[2015,3,24]]}}}