Triangular Clique Based Multilevel Approaches to Identify Protein Functional Modules
Suely Oliveira (University of Iowa)Sang Seok (University of Iowa)
Abstract:
Identifying functional modules is believed to reveal most cellular processes.
There have been many computational approaches to investigate the
underlying biological structures.
A spectral clustering method plays a critical role identifying
functional modules in a yeast protein-protein network in [pothen2005].
One of major obstacles clustering algorithms face and deal with
is the limited information on how close two proteins
with or without interactions are.
We present an unweighted-graph version of a multilevel spectral algorithm
which identifies more protein complexes with less
computational time. Existing multilevel approaches are hampered with
no preliminary knowledge how many levels should be used to expect the best or near best
results.
While existing matching based multilevel algorithms try to merge pairs of nodes,
we here present a new multilevel algorithms which merges groups of three nodes
in triangular cliques.
These new algorithms produce as good clustering results as previously best known matching based
coarsening algorithms. Moreover, our algorithms use only one or two levels of coarsening, so
we can avoid a major weakness of matching based algorithms.
Keywords:
Computing in Biosciences, Data Processing, Numerical Methods (Other), ,
