Biclustering Protein Complex Interactions with a Biclique Finding Algorithm
Authors:
- 1 December 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE International Conference on Data Mining (ICDM)
- No. 15504786,p. 178-187
Abstract
Biclustering has many applications in text mining, Web clickstream mining, and bioinformatics. When data entries are binary, the tightest biclusters become bicliques. We propose a flexible and highly efficient algorithm to compute bicliques. We first generalize the Motzkin-Straus formalism for computing the maximal clique from L1 constraint to Lp constraint, which enables us to provide a generalized Motzkin-Straus formalism for computing maximal-edge bicliques. By adjusting parameters, the algorithm can favor biclusters with more rows less columns, or vice verse, thus increasing the flexibility of the targeted biclusters. We then propose an algorithm to solve the generalized Motzkin-Straus optimization problem. The algorithm is provably convergent and has a computational complexity of O(/E/) where /E/ is the number of edges. Using this algorithm, we bicluster the yeast protein complex interaction network. We find that biclustering protein complexes at the protein level does not clearly reflect the functional linkage among protein complexes in many cases, while biclustering at protein domain level can reveal many underlying linkages. We show several new biologically significant results.Keywords
This publication has 20 references indexed in Scilit:
- A Correspondence Between Maximal Complete Bipartite Subgraphs and Closed Patterns2005
- Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometryNature, 2002
- Functional organization of the yeast proteome by systematic analysis of protein complexesNature, 2002
- A comprehensive two-hybrid analysis to explore the yeast protein interactomeProceedings of the National Academy of Sciences, 2001
- The Elements of Statistical Learning2001
- A comprehensive analysis of protein–protein interactions in Saccharomyces cerevisiaeNature, 2000
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- Continuous Characterizations of the Maximum Clique ProblemMathematics of Operations Research, 1997
- Relaxation labeling networks that solve the maximum clique problem1995
- Maxima for Graphs and a New Proof of a Theorem of TuránCanadian Journal of Mathematics, 1965