Search. Read. Cite.

Easy to search. Easy to read. Easy to cite with credible sources.

Bioinformatics

Year: 2009  |  Volume: 25  |  Issue: 14  |  Page No.: 1814 - 1821

Structure discovery in PPI networks using pattern-based network decomposition

P Bachman and Y. Liu

Abstract

Motivation: 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.

View Fulltext