Biclustering Protein Complex Interactions with a Biclique FindingAlgorithm
Chris H. Q. Ding, Anne Ya Zhang, Stephen R. Holbrook · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2006
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 L 1 constraint to L p 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.It relies on a matrixvector multiplication and runs efficiently on most current computer architectures.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.