Multilevel approaches for large-scale proteomic networks

Abstract

Our multilevel algorithms aim to improve existing graph clustering algorithms which predict protein complexes in large-scale proteomic networks, which are represented as unweighted graphs. Current matching based multilevel algorithms are hampered by low-quality of grouping (coarsening) even though they dramatically reduce computational time. We present a multilevel algorithm with structured analysis of unweighted networks which constructs high-quality groups of nodes merged before applying a clustering algorithm. A 2-core network of a proteomic network is constructed by removing all nodes which have degree less than two recursively. Our multilevel algorithm builds a series of smaller (or coarser) networks from the 2-core network by searching highly dense subgraphs in each level and then a clustering algorithm is applied. The clustering results are passed to the original network with additional fine tuning. All leftover nodes outside the 2-core network are added back after the multilevel algorithm. Compared to existing multilevel algorithm, our multilevel algorithm on 2-core networks shows that nodes in coarser networks have higher accuracy in all supernodes, and clustering results show up to 15% (mostly around 10%) improvements. Moreover, our clustering algorithm uses only one or two levels, so it is free from deciding the number of levels to expect best results.

Keywords:

• Clique
• Multilevel method
• Protein complexes
• Protein–protein interaction

Acknowledgements

We thank all the referees for some corrections and many suggestions about the presentation of this research. We also thank Joe Eichholz and David Stewart for proofreading the last draft. This work was supported in part by NSF ITR grant DMS-0213305.