An Evolutionary Algorithm With Heuristic Operator for Detecting Protein Complexes in Protein Interaction Networks With Negative Controls

Abstract

Computational biology research faces a formidable challenge in the detection of complexes within protein-protein interaction (PPI) networks, critical for unraveling cellular processes, predicting functions of uncharacterized proteins, and diagnosing diseases. While evolutionary algorithms (EAs), particularly state-of-the-art methods, often partition PPI networks based on graph properties or biological semantics, their resilience to noisy or missing interactions remains an underexplored territory. In this paper, we propose a groundbreaking heuristic operator, termed “strong neighbor-node migration”, specifically designed to elevate solution quality during the evolutionary process of our proposed EA. Through the application of EAs, we systematically evaluate the robustness of three single-objective models and two multi-objective models dedicated to addressing the complex detection problem. Our comprehensive assessment spans three well-known PPI networks, including two Saccharomyces cerevisiae datasets and the Human Protein Reference Database. To challenge the models further, we generate artificial networks by introducing varying percentages of noise to the original PPI networks. The experimental results showcase the superiority of the multi-objective model that incorporates our novel heuristic operator, demonstrating enhanced prediction accuracy compared to state-of-the-art models. Encouragingly, we advocate for the expansion of this research to integrate biological information, such as gene ontology. We propose the development of an objective function and heuristic operator based on this biological data, aiming to advance protein complex detection.

Keywords

• Evolutionary algorithm
• multi-objective optimization
• heuristic operator
• protein-protein interaction network
• complex detection