{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T09:35:01Z","timestamp":1790674501190,"version":"4.1.0"},"reference-count":46,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":772,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Biological network comparison software largely relies on the concept of alignment where close matches between the nodes of two or more networks are sought. These node matches are based on sequence similarity and\/or interaction patterns. However, because of the incomplete and error-prone datasets currently available, such methods have had limited success. Moreover, the results of network alignment are in general not amenable for distance-based evolutionary analysis of sets of networks. In this article, we describe Netdis, a topology-based distance measure between networks, which offers the possibility of network phylogeny reconstruction.<\/jats:p>\n               <jats:p>Results: We first demonstrate that Netdis is able to correctly separate different random graph model types independent of network size and density. The biological applicability of the method is then shown by its ability to build the correct phylogenetic tree of species based solely on the topology of current protein interaction networks. Our results provide new evidence that the topology of protein interaction networks contains information about evolutionary processes, despite the lack of conservation of individual interactions. As Netdis is applicable to all networks because of its speed and simplicity, we apply it to a large collection of biological and non-biological networks where it clusters diverse networks by type.<\/jats:p>\n               <jats:p>Availability and implementation: The source code of the program is freely available at http:\/\/www.stats.ox.ac.uk\/research\/proteins\/resources.<\/jats:p>\n               <jats:p>Contact: \u00a0w.ali@stats.ox.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu447","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T11:23:57Z","timestamp":1409052237000},"page":"i430-i437","source":"Crossref","is-referenced-by-count":60,"title":["Alignment-free protein interaction network comparison"],"prefix":"10.1093","volume":"30","author":[{"given":"Waqar","family":"Ali","sequence":"first","affiliation":[{"name":"1 Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and 2Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tiago","family":"Rito","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and 2Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gesine","family":"Reinert","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and 2Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fengzhu","family":"Sun","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and 2Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charlotte M.","family":"Deane","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and 2Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,8,22]]},"reference":[{"key":"2023012711542683600_btu447-B1","doi-asserted-by":"crossref","first-page":"2296","DOI":"10.1039\/c004430j","article-title":"Evolutionary analysis reveals low coverage as the major challenge for protein interaction network alignment","volume":"6","author":"Ali","year":"2010","journal-title":"Mol. Biosyst."},{"key":"2023012711542683600_btu447-B2","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1093\/bioinformatics\/btt713","article-title":"Beams: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks","volume":"30","author":"Alkan","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012711542683600_btu447-B3","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023012711542683600_btu447-B4","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711542683600_btu447-B5","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1016\/j.jmb.2007.03.013","article-title":"The identification of similarities between biological networks: application to the metabolome and interactome","volume":"369","author":"Cootes","year":"2007","journal-title":"J. Mol. Biol."},{"key":"2023012711542683600_btu447-B6","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1074\/mcp.M100037-MCP200","article-title":"Protein interactions: two methods for assessment of the reliability of high throughput observations","volume":"1","author":"Deane","year":"2002","journal-title":"Mol. Cell. Proteomics"},{"key":"2023012711542683600_btu447-B7","first-page":"343","article-title":"On the evolution of random graphs","volume":"38","author":"Erd\u00f6s","year":"1961","journal-title":"Bull. Inst. Internat. Statist."},{"key":"2023012711542683600_btu447-B8","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1089\/cmb.2009.0099","article-title":"Automatic parameter learning for multiple network alignment","volume":"16","author":"Flannick","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012711542683600_btu447-B9","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1186\/1471-2105-13-148","article-title":"Surprising results on phylogenetic tree building methods based on molecular sequences","volume":"13","author":"Gonnet","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012711542683600_btu447-B10","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1093\/bioinformatics\/btt717","article-title":"A combinatorial approach to graphlet counting","volume":"30","author":"Hoevar","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012711542683600_btu447-B11","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1093\/bioinformatics\/btt715","article-title":"Netcoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks","volume":"30","author":"Hu","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012711542683600_btu447-B12","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01908075","article-title":"Comparing partitions","volume":"2","author":"Hubert","year":"1985","journal-title":"J. Classif."},{"key":"2023012711542683600_btu447-B13","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/sysbio\/42.3.247","article-title":"Success of phylogenetic methods in the four-taxon case","volume":"42","author":"Huelsenbeck","year":"1993","journal-title":"Syst. Biol."},{"key":"2023012711542683600_btu447-B14","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1038\/msb.2011.99","article-title":"Differential network biology","volume":"8","author":"Ideker","year":"2012","journal-title":"Mol. Systems Biol."},{"key":"2023012711542683600_btu447-B15","doi-asserted-by":"crossref","first-page":"D767","DOI":"10.1093\/nar\/gkn892","article-title":"Human Protein Reference Database\u20132009 update","volume":"37","author":"Keshava Prasad","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012711542683600_btu447-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":"2023012711542683600_btu447-B17","doi-asserted-by":"crossref","first-page":"e1002645","DOI":"10.1371\/journal.pcbi.1002645","article-title":"What evidence is there for the homology of protein-protein interactions?","volume":"8","author":"Lewis","year":"2012","journal-title":"PLoS Comput. Biol."},{"key":"2023012711542683600_btu447-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":"2023012711542683600_btu447-B19","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.jtbi.2011.06.020","article-title":"New powerful statistics for alignment-free sequence comparison under a pattern transfer model","volume":"284","author":"Liu","year":"2011","journal-title":"J. Theor. Biol."},{"key":"2023012711542683600_btu447-B20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1186\/1471-2148-11-133","article-title":"Evidence for the additions of clustered interacting nodes during the evolution of protein interaction networks from network motifs","volume":"11","author":"Liu","year":"2011","journal-title":"BMC Evol. Biol."},{"key":"2023012711542683600_btu447-B21","doi-asserted-by":"crossref","first-page":"2120","DOI":"10.1101\/gr.205301","article-title":"Identification of potential interaction networks using sequence-based searches for conserved protein-protein interactions or \u201cinterologs\u201d","volume":"11","author":"Matthews","year":"2001","journal-title":"Genome Res."},{"key":"2023012711542683600_btu447-B22","doi-asserted-by":"crossref","first-page":"3192","DOI":"10.1073\/pnas.0409515102","article-title":"Inferring network mechanisms: the drosophila melanogaster protein interaction network","volume":"102","author":"Middendorf","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711542683600_btu447-B23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"Newman","year":"2010","edition":"1st edn"},{"key":"2023012711542683600_btu447-B24","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.86.036104","article-title":"Taxonomies of networks from community structure","volume":"86","author":"Onnela","year":"2012","journal-title":"Phys. Rev. E"},{"key":"2023012711542683600_btu447-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":"2023012711542683600_btu447-B26","volume-title":"Algebraic Models for Social Networks. Structural Analysis in the Social Sciences","author":"Pattison","year":"1993"},{"key":"2023012711542683600_btu447-B27","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random Geometric Graphs (Oxford Studies in Probability)","author":"Penrose","year":"2003"},{"key":"2023012711542683600_btu447-B28","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1093\/bioinformatics\/bts119","article-title":"Pinalog: a novel approach to align protein interaction networks\u2014implications for complex detection and function prediction","volume":"28","author":"Phan","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012711542683600_btu447-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":"2023012711542683600_btu447-B30","volume-title":"Geometric Evolutionary Dynamics of Protein Interaction Networks","author":"Pr\u017eulj","year":"2010"},{"key":"2023012711542683600_btu447-B31","volume-title":"R: A Language and Environment for Statistical Computing","author":"R Core Team","year":"2013"},{"key":"2023012711542683600_btu447-B32","doi-asserted-by":"crossref","first-page":"290","DOI":"10.2976\/1.3167215","article-title":"From evidence to inference: probing the evolution of protein interaction networks","volume":"3","author":"Ratmann","year":"2009","journal-title":"HFSP J."},{"key":"2023012711542683600_btu447-B33","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1089\/cmb.2009.0198","article-title":"Alignment-free sequence comparison (I): statistics and power","volume":"16","author":"Reinert","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012711542683600_btu447-B34","doi-asserted-by":"crossref","first-page":"3173","DOI":"10.1073\/pnas.0500130102","article-title":"Lasting impressions: Motifs in protein-protein maps may provide footprints of evolutionary events","volume":"102","author":"Rice","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711542683600_btu447-B35","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":"2023012711542683600_btu447-B36","doi-asserted-by":"crossref","first-page":"785","DOI":"10.1089\/cmb.2012.0054","article-title":"The importance of age and high degree, in protein-protein interaction networks","volume":"19","author":"Rito","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023012711542683600_btu447-B37","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":"2023012711542683600_btu447-B38","doi-asserted-by":"crossref","first-page":"D5","DOI":"10.1093\/nar\/gkn741","article-title":"Database resources of the National Center for Biotechnology Information","volume":"37","author":"Sayers","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012711542683600_btu447-B39","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1093\/bioinformatics\/btq706","article-title":"phangorn: phylogenetic analysis in r","volume":"27","author":"Schliep","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012711542683600_btu447-B40","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":"2023012711542683600_btu447-B41","doi-asserted-by":"crossref","first-page":"e1001050","DOI":"10.1371\/journal.pcbi.1001050","article-title":"Measuring the evolutionary rewiring of biological networks","volume":"7","author":"Shou","year":"2011","journal-title":"PLoS Comput. Biol."},{"key":"2023012711542683600_btu447-B42","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":"2023012711542683600_btu447-B43","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"28","author":"Sokal","year":"1958","journal-title":"Univ. Kans. Sci. Bull."},{"key":"2023012711542683600_btu447-B44","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1089\/cmb.2012.0228","article-title":"Alignment-free sequence comparison based on next-generation sequencing reads","volume":"20","author":"Song","year":"2013","journal-title":"J. Comput. Biol."},{"key":"2023012711542683600_btu447-B45","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1038\/nrg2267","article-title":"The road to modularity","volume":"8","author":"Wagner","year":"2007","journal-title":"Nat. Rev. Genet."},{"key":"2023012711542683600_btu447-B46","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1101\/gad.1528707","article-title":"Getting connected: analysis and principles of biological networks","volume":"21","author":"Zhu","year":"2007","journal-title":"Genes Dev."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i430\/48927381\/bioinformatics_30_17_i430.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i430\/48927381\/bioinformatics_30_17_i430.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:29:23Z","timestamp":1674822563000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/17\/i430\/199959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,22]]},"references-count":46,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu447","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,9,1]]},"published":{"date-parts":[[2014,8,22]]}}}