AHeuristic Strategy for Improving the Performance of Evolutionary Based Complex Detection in Protein-Protein Interaction Networks

Abstract

One of the most interested problems that recently attracts many research investigations in Protein-protein interactions (PPI) networks is complex detection problem. Detecting natural divisions in such complex networks is proved to be extremely NP-hard problem wherein, recently, the field of Evolutionary Algorithms (EAs) reveals positive results. The contribution of this work is to introduce a heuristic operator, called protein-complex attraction and repulsion, which is especially tailored for the complex detection problem and to enable the EA to improve its detection ability. The proposed heuristic operator is designed to fine-grain the structure of a complex by dividing it into two more complexes, each being distinguished with a core protein. Then, it is possible for each of the remaining proteins associated with the original coarse-grained complex to repulse from one of the new generated complexes while attracted by the core protein of the second complex. The topology-based complex detection models presented in the literature are adopted to inter-play with the proposed heuristic operator inside the EA general framework. To assess the performance of the EA when coupled with the proposed heuristic operator, the well known Saccaromycaes Cerevisiae yeast PPI network and one reference set of benchmark complexes created from MIPS are used in the experiments. The results prove the positive impact of the heuristic operator to harness the strength of almost all adopted EA models.