title: Structure discovery in PPI networks using pattern-based network decomposition.
abstract: BACKGROUND
  The large, complex networks of interactions between proteins provide a lens through which one can examine the structure and function of biological systems. Previous analyses of these continually growing networks have primarily followed either of two approaches: large-scale statistical analysis of holistic network properties, or small-scale analysis of local topological features. Meanwhile, investigation of meso-scale network structure (above that of individual functional modules, while maintaining the significance of individual proteins) has been hindered by the computational complexity of structural search in networks. Examining protein-protein interaction (PPI) networks at the meso-scale may provide insights into the presence and form of relationships between individual protein complexes and functional modules.
  
  
  RESULTS
  In this article, we present an efficient algorithm for performing sub-graph isomorphism queries on a network and show its computational advantage over previous methods. We also present a novel application of this form of topological search which permits analysis of a network's structure at a scale between that of individual functional modules and that of network-wide properties. This analysis provides support for the presence of hierarchical modularity in the PPI network of Saccharomyces cerevisiae.
authors.affiliation: Department of Computer Science and Department of Molecular Biology, University of Texas at Dallas, Richardson, TX 75083-0688, USA.
authors.forename: Philip
authors.initials: P
authors.lastname: Bachman
authors.forename: Ying
authors.initials: Y
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D025941:Protein Interaction Mapping; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry* / Q000378:metabolism
chemical_list: D029701:Saccharomyces cerevisiae Proteins