title: Alignment-free protein interaction network comparison.
abstract: BACKGROUND
  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.
  
  
  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.
  
  
  METHODS
  The source code of the program is freely available at http://www.stats.ox.ac.uk/research/proteins/resources.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA.
authors.forename: Waqar
authors.initials: W
authors.lastname: Ali
authors.affiliation: Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA.
authors.forename: Tiago
authors.initials: T
authors.lastname: Rito
authors.affiliation: Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA.
authors.forename: Gesine
authors.initials: G
authors.lastname: Reinert
authors.affiliation: Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA.
authors.forename: Fengzhu
authors.initials: F
authors.lastname: Sun
authors.affiliation: Department of Statistics, University of Oxford, Oxford OX1 3TG, UK and Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, CA 90089-2910, USA.
authors.forename: Charlotte M
authors.initials: CM
authors.lastname: Deane
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D006801:Humans; D010802:Phylogeny; D025941:Protein Interaction Mapping / Q000379:methods*