Robustness evaluation of Evolutionary-based complex detection algorithms for protein interaction networks with negative control

Background: One of the most significant areas of current computational biology research is the complex detection in protein-protein interaction (PPI) networks due to their critical importance in understanding life at the cellular level, predicting the functions of as-yet-uncharacterized proteins, and diagnosing diseases. Existing state-of-the-art methods, mainly, evolutionary algorithms (EA), partition PPI networks into complexes either based on the graph properties of PPI networks or on their biological semantics. Unfortunately, up to now little interest has been paid to investigate the robustness of these state-of-the-art EAs in unraveling PPI networks with noisy or missing interactions. Results: : In this paper, we adopted EAs to examine the robustness of three single objective models and two multi-objective models that are used to define the complex detection problem. Two well-known Saccharomyces cerevisiae (yeast) PPI networks and two benchmark sets of complexes were used to investigate the robustness of these EA-based complex detection algorithms. Furthermore, several artificial networks are generated by perturbing the original PPI network with different percentage of noise. Conclusions: : Experimental results show that the multi-objective model achieves a higher level of prediction accuracy than other models. We encourage to extend this work to include biological information (i.e., a gene ontology) and design the objective function and heuristic operator based on these biological data for detecting protein complexes.