title: Dense graphlet statistics of protein interaction and random networks.
abstract: Understanding evolutionary dynamics from a systemic point of view crucially depends on knowledge about how evolution affects size and structure of the organisms' functional building blocks (modules). It has been recently reported that statistics over sparse PPI graphlets can robustly monitor such evolutionary changes. However, there is abundant evidence that in PPI networks modules can be identified with highly interconnected (dense) and/or bipartite subgraphs. We count such dense graphlets in PPI networks by employing recently developed search strategies that render related inference problems tractable. We demonstrate that corresponding counting statistics differ significantly between prokaryotes and eukaryotes as well as between "real" PPI networks and scale free network emulators. We also prove that another class of emulators, the low-dimensional geometric random graphs (GRGs) cannot contain a specific type of motifs, complete bipartite graphs, which are abundant in PPI networks.
authors.affiliation: School of Computing Science, Simon Fraser University.
authors.forename: R
authors.initials: R
authors.lastname: Colak
authors.forename: F
authors.initials: F
authors.lastname: Hormozdiari
authors.forename: F
authors.initials: F
authors.lastname: Moser
authors.forename: A
authors.initials: A
authors.lastname: Schönhuth
authors.forename: J
authors.initials: J
authors.lastname: Holman
authors.forename: M
authors.initials: M
authors.lastname: Ester
authors.forename: S C
authors.initials: SC
authors.lastname: Sahinalp
mesh_terms: D001699:Biometry; D029968:Escherichia coli Proteins / Q000737:chemistry / Q000235:genetics; D019143:Evolution, Molecular; D008954:Models, Biological; D054730:Protein Interaction Domains and Motifs; D025941:Protein Interaction Mapping / Q000706:statistics & numerical data*; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics
chemical_list: D029968:Escherichia coli Proteins; D029701:Saccharomyces cerevisiae Proteins