Structure discovery in PPI networks using pattern-based network decomposition.
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.
Bachman
Philip
P
Department of Computer Science and Department of Molecular Biology, University of Texas at Dallas, Richardson, TX 75083-0688, USA.
Liu
Ying
Y
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D025941:Protein Interaction Mapping; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry* / Q000378:metabolism
D029701:Saccharomyces cerevisiae Proteins