Module overlapping structure detection in PPI using an improved link similarity-based Markov clustering algorithm

The identification and analysis of functional modules in protein–protein interaction (PPI) networks provide insight into understanding the organization and function of biological systems. A lot of overlapping structures are shared by the functional modules in PPI networks, which indicates there are some proteins play indispensable roles in different biological processes. Markov clustering (MCL) is a popular algorithm for clustering networks in bioinformatics. In this paper, to identify the overlapping structures among the functional modules and find more modules with biological significance in PPI networks, we propose a Markov clustering algorithm based on link similarity (MLS). First of all, the weighted link similarity is calculated and the link similarity matrix which measures the association strength of the protein interactions can be gotten. Then, the link similarity matrix is divided by applying Markov clustering, and the clustering results are mapped to original networks to analyze the protein modules. The method has been experimented on three databases, including DIP, Gavin and Krogan. Our results show that the MLS cannot only accurately identify the functional modules, but also outperform the original MCL algorithm and the F-measure value improved 5–10% compared with it.