A "seed-refine" algorithm for detecting protein complexes from protein interaction data
1Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA. ppei@cse.buffalo.edu
Abstract:
New technology advances in large-scale protein-protein interaction detection provide researchers an initial view of proteins on a global scale. These massive data sets provide a valuable source for elucidating the biomolecular mechanism in the cell. In this paper, we investigate the problem of protein complex detection from noisy protein interaction data, i.e., finding the subsets of proteins that are closely coupled via protein interactions. We identify the challenges and propose a "seed-refine" approach. We propose a novel statistically meaningful subgraph quality measure, a two-layer seeding heuristic to find good seeds, and a novel subgraph refinement method that controls the overlap between subgraphs. Experiments show the desirable properties of our subgraph quality measure and the effectiveness of our "seed-refine" algorithm.
Related Concept Videos
Protein Networks
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
Protein-protein Interfaces
Protein-Protein Interfaces
Protein Complexes with Interchangeable Parts
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
Protein Complexes with Interchangeable Parts
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...


