Back to Search
Start Over
A novel graph clustering method with a greedy heuristic search algorithm for mining protein complexes from dynamic and static PPI networks
- Source :
- Information Sciences. 522:275-298
- Publication Year :
- 2020
- Publisher :
- Elsevier BV, 2020.
-
Abstract
- Discovering protein complexes from protein-protein interaction (PPI) networks is one of the primary tasks in bioinformatics. However, most of the state-of-the-art methods still face some challenges, such as the inability to discover overlapping protein complexes, failure to consider the inherent structure of real protein complexes, and non-utilization of biological information. Based on the above mentioned aspects, we present a novel graph clustering method with a greedy heuristic search algorithm for mining protein complexes using a new clustering model in dynamic and static weighted PPI networks (named MPC-C). First, MPC-C constructed dynamic and static weighted PPI networks by combining biological and topological information. Second, initial clusters were obtained using core and multifunctional proteins, following which we proposed a greedy heuristic search algorithm to expand each initial cluster and form candidate protein complexes in dynamic and static weighted PPI networks. Finally, unreliable and highly overlapping protein complexes were discarded. To demonstrate the performance of MPC-C, we tested this method on five PPI networks and compared it with nine other effective methods. The experimental results indicate that MPC-C outperformed the other state-of-the-art methods with respect to various computational and biologically relevant metrics.
- Subjects :
- Structure (mathematical logic)
Information Systems and Management
Computer science
Quantitative Biology::Molecular Networks
05 social sciences
050301 education
02 engineering and technology
computer.software_genre
Computer Science Applications
Theoretical Computer Science
ComputingMethodologies_PATTERNRECOGNITION
Artificial Intelligence
Control and Systems Engineering
Search algorithm
Core (graph theory)
0202 electrical engineering, electronic engineering, information engineering
Cluster (physics)
020201 artificial intelligence & image processing
Data mining
Greedy algorithm
Cluster analysis
0503 education
computer
Software
Clustering coefficient
Subjects
Details
- ISSN :
- 00200255
- Volume :
- 522
- Database :
- OpenAIRE
- Journal :
- Information Sciences
- Accession number :
- edsair.doi...........946683ff7f5d3a02d93058dc2c67a169