Topology-Based Modularity and Modularity Density for Detecting Protein Complexes: A Comparative Study

Abstract

     Binary relations or interactions among bio-entities, such as proteins, set up the essential part of any living biological system. Protein-protein interactions are usually structured in a graph data structure called "protein-protein interaction networks" (PPINs). Analysis of PPINs into complexes tries to lay out the significant knowledge needed to answer many unresolved questions, including how cells are organized and how proteins work. However, complex detection problems fall under the category of non-deterministic polynomial-time hard (NP-Hard) problems due to their computational complexity. To accommodate such combinatorial explosions, evolutionary algorithms (EAs) are proven effective alternatives to heuristics in solving NP-hard problems. The main aim of this study is to make a close examination of the performance of the EAs where modularity and modularity density are selected as two different objective functions. Topology-based modularity and topology-based modularity density are designed to examine the detection ability of the EAs and to compare their performance. To conduct the experiments, two yeast Saccharomyces cerevisiae PPINs are used and evaluated under nine evaluation metrics. The results reveal the potential impact of the topology-based modularity density to outperform the counterpart modularity functions in almost all evaluation metrics.