Functional module identification by block modeling using simulated annealing with path relinking
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Identifying functional modules and understanding their organization in biological networks is of great importance. Recently, module identification by block modeling has demonstrated its advantages over the existing algorithms only considering topologically "cohesive" modules. In this paper, we aim to identify biologically meaningful functional modules by not only considering topologically "cohesive"modules but also taking into account the modules with nodes sparsely connected but sharing similar interaction patterns. In our adopted block modeling framework, we propose a novel efficient optimization algorithm by combining Simulated Annealing (SA) and Path Relinking (PR) to solve this difficult combinatorial optimization problem. We have evaluated the performance of our algorithm on a set of synthetic benchmark networks and a human protein-protein interaction (PPI) network. Our results show that our new SAPR algorithm achieves higher accuracy than existing state-ofthe-art algorithms. The new algorithm also has significantly reduced computation time compared to the traditional SA algorithm with competitive accuracy. Preliminary results for identifying functional modules in the human PPI network and the comparison with the commonly adopted Markov Clustering (MCL) algorithm have demonstrated the potential of our algorithm to discover new types of modules, within which proteins are sparsely connected but with significantly enriched biological functionalities. Copyright 2012 ACM.
name of conference
Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine
