Dynamical Systems for Discovering Protein Complexes and Functional Modules from Biological Networks

• Published in: IEEE/ACM transactions on computational biology and bioinformatics 2007-04, Vol.4 (2), p.233-250
• Main Authors: Li, Wenyuan, Liu, Ying, Huang, Hung-Chung, Peng, Yanxiong, Lin, Yongjing, Ng, Wee-Keong, Ong, Kok-Leong
• Format: Article
• Language: English
• Subjects: Algorithms; Bioinformatics; bioinformatics databases; Biological system modeling; Biology computing; Cellular networks; Computer science; Computer Simulation; Data Interpretation, Statistical; evolutionary computing; Fungi; Gene Expression - physiology; Genomics; Graph algorithms; Large-scale systems; Models, Biological; neural nets; Protein engineering; Protein Interaction Mapping - methods; Proteome - metabolism; Signal Transduction - physiology; Standard deviation; Studies; Throughput
• ISSN: 1545-5963; 1557-9964
• DOI: 10.1109/TCBB.2007.070210

Recent advances in high throughput experiments and annotations via published literature have provided a wealth of interaction maps of several biomolecular networks, including metabolic, protein-protein, and protein-DNA interaction networks. The architecture of these molecular networks reveals important principles of cellular organization and molecular functions. Analyzing such networks, i.e., discovering dense regions in the network, is an important way to identify protein complexes and functional modules. This task has been formulated as the problem of finding heavy subgraphs, the heaviest k-subgraph problem (k-HSP), which itself is NP-hard. However, any method based on the k-HSP requires the parameter k and an exact solution of k-HSP may still end up as a "spurious" heavy subgraph, thus reducing its practicability in analyzing large scale biological networks. We proposed a new formulation, called the rank-HSP, and two dynamical systems to approximate its results. In addition, a novel metric, called the standard deviation and mean ratio (SMR), is proposed for use in "spurious" heavy subgraphs to automate the discovery by setting a fixed threshold. Empirical results on both the simulated graphs and biological networks have demonstrated the efficiency and effectiveness of our proposal