B3Clustering: Identifying Protein Complexes from Protein-Protein Interaction Network

Cluster analysis is one of most important challenges for data mining in the modern Biology. The advance of experimental technologies have produced large amount of binary protein-protein interaction data, but it is hard to find protein complexes in vitro.We introduce new algorithm called B3Clustering which detects densely connected subgraphs from the complicated and noisy graph. B3Clustering finds clusters by adjusting the density of subgraphs to be flexible according to its size, because the more vertices the cluster has, the less dense it becomes. B3Clustering bisects the paths with distance of 3 into two groups to select vertices from each group.We experiment B3Clustering and two other clustering methods in three different PPI networks. Then, we compare the resultant clusters from each method with benchmark complexes called CYC2008. The experimental result supports the efficiency and robustness of B3Clustering for protein complex prediction in PPI networks.