Accuracy improvement in protein complex prediction from protein interaction networks by refining cluster overlaps

Background: recent computational techniques have facilitated analyzing genome-wide protein-protein interaction data for several model organisms. various graph-clustering algorithms have been applied to protein interaction networks on the genomic scale for predicting the entire set of potential protein complexes. in particular,the density-based clustering algorithms which are able to generate overlapping clusters,i.e. the clusters sharing a set of nodes,are well-suited to protein complex detection because each protein could be a member of multiple complexes. however,their accuracy is still limited because of complex overlap patterns of their output clusters. results: we present a systematic approach of refining the overlapping clusters identified from protein interaction networks. we have designed novel metrics to assess cluster overlaps: overlap coverage and overlapping consistency. we then propose an overlap refinement algorithm. it takes as input the clusters produced by existing density-based graph-clustering methods and generates a set of refined clusters by parameterizing the metrics. to evaluate protein complex prediction accuracy,we used the f-measure by comparing each refined cluster to known protein complexes. the experimental results with the yeast protein-protein interaction data sets from biogrid and dip demonstrate that accuracy on protein complex prediction has increased significantly after refining cluster overlaps. conclusions: the effectiveness of the proposed cluster overlap refinement approach for protein complex detection has been validated in this study. analyzing overlaps of the clusters from protein interaction networks is a crucial task for understanding of functional roles of proteins and topological characteristics of the functional systems. © 2012 chiam and cho.