52
Views
7
CrossRef citations to date
0
Altmetric
Original Articles

Multilevel approaches for large-scale proteomic networks

&
Pages 683-695 | Received 30 Sep 2006, Accepted 08 Mar 2007, Published online: 02 Jul 2007
 

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.

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.