title: How threshold behaviour affects the use of subgraphs for network comparison.
abstract: BACKGROUND
  A wealth of protein-protein interaction (PPI) data has recently become available. These data are organized as PPI networks and an efficient and biologically meaningful method to compare such PPI networks is needed. As a first step, we would like to compare observed networks to established network models, under the aspect of small subgraph counts, as these are conjectured to relate to functional modules in the PPI network. We employ the software tool GraphCrunch with the Graphlet Degree Distribution Agreement (GDDA) score to examine the use of such counts for network comparison.
  
  
  RESULTS
  Our results show that the GDDA score has a pronounced dependency on the number of edges and vertices of the networks being considered. This should be taken into account when testing the fit of models. We provide a method for assessing the statistical significance of the fit between random graph models and biological networks based on non-parametric tests. Using this method we examine the fit of Erdös-Rényi (ER), ER with fixed degree distribution and geometric (3D) models to PPI networks. Under these rigorous tests none of these models fit to the PPI networks. The GDDA score is not stable in the region of graph density relevant to current PPI networks. We hypothesize that this score instability is due to the networks under consideration having a graph density in the threshold region for the appearance of small subgraphs. This is true for both geometric (3D) and ER random graph models. Such threshold behaviour may be linked to the robustness and efficiency properties of the PPI networks.
authors.affiliation: Department of Statistics, University of Oxford, Oxford, UK. tiago@stats.ox.ac.uk
authors.forename: Tiago
authors.initials: T
authors.lastname: Rito
authors.forename: Zi
authors.initials: Z
authors.lastname: Wang
authors.forename: Charlotte M
authors.initials: CM
authors.lastname: Deane
authors.forename: Gesine
authors.initials: G
authors.lastname: Reinert
mesh_terms: D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D006801:Humans; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D012441:Saccharomyces cerevisiae / Q000235:genetics; D015398:Signal Transduction; D012984:Software
references.citation: BMC Genomics. 2006 May 05;7:108
references.pmid: 16677373
references.citation: Bioinformatics. 2008 Jul 1;24(13):i241-9
references.pmid: 18586721
references.citation: J R Soc Interface. 2006 Oct 22;3(10):711-6
references.pmid: 16971339
references.citation: Brief Funct Genomic Proteomic. 2008 Mar;7(2):147-56
references.pmid: 18443014
references.citation: PLoS Comput Biol. 2007 Jul;3(7):e118
references.pmid: 17616981
references.citation: Bioinformatics. 2007 Jan 15;23(2):e177-83
references.pmid: 17237089
references.citation: PLoS One. 2009 Jun 26;4(6):e5967
references.pmid: 19557139
references.citation: Curr Opin Struct Biol. 2003 Apr;13(2):193-202
references.pmid: 12727512
references.citation: Nat Biotechnol. 2006 Apr;24(4):427-33
references.pmid: 16601728
references.citation: Proc Natl Acad Sci U S A. 2000 Feb 1;97(3):1143-7
references.pmid: 10655498
references.citation: Nature. 2005 Oct 20;437(7062):1173-8
references.pmid: 16189514
references.citation: Proc Natl Acad Sci U S A. 2008 May 13;105(19):6959-64
references.pmid: 18474861
references.citation: Science. 2002 Oct 25;298(5594):824-7
references.pmid: 12399590
references.citation: Nature. 2002 May 23;417(6887):399-403
references.pmid: 12000970
references.citation: Bioinformatics. 2004 Dec 12;20(18):3508-15
references.pmid: 15284103
references.citation: BMC Bioinformatics. 2008 Jan 30;9:70
references.pmid: 18230190
references.citation: Cell. 2005 Sep 23;122(6):957-68
references.pmid: 16169070
references.citation: Annu Int Conf IEEE Eng Med Biol Soc. 2009;2009:4166-70
references.pmid: 19964621
references.citation: Nat Genet. 2002 May;31(1):64-8
references.pmid: 11967538
references.citation: Nature. 1999 Dec 2;402(6761 Suppl):C47-52
references.pmid: 10591225
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Jul;66(1 Pt 2):016121
references.pmid: 12241440