Improving the performance of evolutionary-based complex detection models in protein–protein interaction networks

Detecting functional modules in protein–protein interaction (PPI) networks is an important and ongoing challenge in computational biology. To partition a PPI network into complexes, most existing state-of-the-art methods, including evolutionary algorithms (EAs), are based solely on either very general graphical properties or very specific biological semantics of PPI networks or both. Despite the strength and the additional predictive improvements introduced by EA-based complex detection methods and apart from the specific biological properties of PPI networks, more inherent topological properties of protein complexes are rarely explored in these approaches. Moreover, many of these EAs view and define complex detection problem as a single-objective optimization problem. In this paper, we introduce a new multi-objective optimization model for formulating complex detection problem. A heuristic perturbation operator, called protein complex attraction and repulsion, is also introduced to improve the quality of a given solution. To the best of our knowledge, this is the first attempt to exploit the topological structure of proteins interactions in both problem formulation and complex perturbation. To demonstrate the effectiveness of the proposed multi-objective evolutionary-based complex detection algorithm, two well-known PPI networks and two reference sets of benchmark complexes created from MIPS are used in the experiments. Moreover, new random networks are generated from the Saccharomyces cerevisiae (yeast) PPI network to investigate the impact of perturbing protein interactions on the final performance of the proposed algorithm against counterpart algorithms. In comparison with several state-of-the-art methods, experimental results reveal that the proposed algorithm achieves more predictive level of matched protein complexes. Moreover, the results demonstrate the positive impact of injecting the proposed heuristic perturbation operator in improving the quality of the detected complexes obtained by all state-of-the-art EA-based methods.