A new evolutionary algorithm with locally assisted heuristic for complex detection in protein interaction networks

Abstract The detection of protein complexes is an essential NP-hard problem in protein-protein interaction networks (PPI). Modularity, community score, ratio cut, and internal density are some examples of the state-of-the-art optimization models. The contribution of this paper is to develop a heuristic approach that can serve as a common locally assisted optimization model to reinforce the reliability of all these complex detection models. The foundation of the proposed heuristic approach hypothesizes a possible decomposition of a pair of proteins, according to their interactions, into two different types. A pair of proteins is classified as either intra-delineation pair or inter-delineation pair depending on their topological similarity. Two proteins with high topological similarity are favored to form an intra-delineation structure; otherwise, they can form an inter-delineation pair. Therefore, the detection for a better complex structure should express more intra-delineation pairs and less inter-delineation pairs within complexes while more inter-delineation pairs and less intra-delineation pairs among separate complexes. The proposed heuristic operator is then injected into the framework of single objective and multi-objective evolutionary algorithms (EAs) while existing complex detection models work as EA optimization templates. In the experiments, we analyze the performance of the detection models when applied to the publicly available yeast protein networks. Results give clear argument to the positive impact of the proposed heuristic approach to considerably improve the detection ability of the existing optimization models, and further to provide more competitive results than a recently developed heuristic approach.