An enhanced Markov clustering method for detecting protein complexes

With the recent high-throughput methods, large datasets of experimentally detected pairwise protein-protein interactions are generated. However, these data suffer from noise, reducing the quality of the information they bring (identification of protein complexes). This paper introduces a novel methodology for detecting protein complexes in a protein-protein interaction graph. Our method initially uses the Markov clustering algorithm and then filters the derived results in order to obtain the best set of clusters that represent protein complexes. The efficiency of our method is shown in experimental results derived from 7 different yeast protein interaction datasets. Moreover, comparisons with 4 other algorithms are performed proving that our method predicts known protein complexes, recorded in the MIPS database, more accurately.