Mining the Largest Quasi-clique in Human Protein Interactome

A clique is a complete subgraph of a graph. Often, a clique is interpreted as a dense module of vertices within a graph. However, in many real-world situations, the classical problem of finding a clique is required to be relaxed. This motivates the problem of finding quasicliques that are almost complete subgraphs of a graph. In sparse and very large scale-free networks, the problem of finding the largest quasi-clique becomes hard to manage with the existing approaches. Here, we propose a heuristic algorithm in this paper for locating the largest quasi-clique from the human protein-protein interaction networks. The results show promise in computational biology research by the exploration of significant protein modules