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 com...

Full description

Saved in:
Bibliographic Details
Main Authors: Bhattacharyya, M., Bandyopadhyay, S.
Format: Conference Proceeding
Language:English
Subjects:
Adaptive systems
Computational biology
Computer network management
Heuristic algorithms
Humans
Intelligent systems
Machine intelligence
Organisms
Proteins
Web sites
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/ICAIS.2009.39