How threshold behaviour affects the use of subgraphs for network comparison.
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.
Rito
Tiago
T
Department of Statistics, University of Oxford, Oxford, UK. tiago@stats.ox.ac.uk
Wang
Zi
Z
Deane
Charlotte M
CM
Reinert
Gesine
G
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
BMC Genomics. 2006 May 05;7:108
16677373
Bioinformatics. 2008 Jul 1;24(13):i241-9
18586721
J R Soc Interface. 2006 Oct 22;3(10):711-6
16971339
Brief Funct Genomic Proteomic. 2008 Mar;7(2):147-56
18443014
PLoS Comput Biol. 2007 Jul;3(7):e118
17616981
Bioinformatics. 2007 Jan 15;23(2):e177-83
17237089
PLoS One. 2009 Jun 26;4(6):e5967
19557139
Curr Opin Struct Biol. 2003 Apr;13(2):193-202
12727512
Nat Biotechnol. 2006 Apr;24(4):427-33
16601728
Proc Natl Acad Sci U S A. 2000 Feb 1;97(3):1143-7
10655498
Nature. 2005 Oct 20;437(7062):1173-8
16189514
Proc Natl Acad Sci U S A. 2008 May 13;105(19):6959-64
18474861
Science. 2002 Oct 25;298(5594):824-7
12399590
Nature. 2002 May 23;417(6887):399-403
12000970
Bioinformatics. 2004 Dec 12;20(18):3508-15
15284103
BMC Bioinformatics. 2008 Jan 30;9:70
18230190
Cell. 2005 Sep 23;122(6):957-68
16169070
Annu Int Conf IEEE Eng Med Biol Soc. 2009;2009:4166-70
19964621
Nat Genet. 2002 May;31(1):64-8
11967538
Nature. 1999 Dec 2;402(6761 Suppl):C47-52
10591225
Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Jul;66(1 Pt 2):016121
12241440