Logo image
Back
Multilevel approaches for large-scale proteomic networks
Journal article   Open access   Peer reviewed

Multilevel approaches for large-scale proteomic networks

S Oliveira and S.-C Seok
International journal of computer mathematics, Vol.84(5), pp.683-695
05/01/2007
DOI: 10.1080/00207160701332382
url
https://doi.org/10.1080/00207160701332382View
Published (Version of record) Open Access

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.
 Clique Multilevel method Protein-protein interaction Protein complexes

Details

Metrics

26 Record Views
5 Times Cited - Web of Science
Logo image