A max-flow-based approach to the identification of protein complexes using protein interaction and microarray data.
The emergence of high-throughput technologies leads to abundant protein-protein interaction (PPI) data and microarray gene expression profiles, and provides a great opportunity for the identification of novel protein complexes using computational methods. By combining these two types of data, we propose a novel Graph Fragmentation Algorithm (GFA) for protein complex identification. Adapted from a classical max-flow algorithm for finding the (weighted) densest subgraphs, GFA first finds large (weighted) dense subgraphs in a protein-protein interaction network, and then, breaks each such subgraph into fragments iteratively by weighting its nodes appropriately in terms of their corresponding log-fold changes in the microarray data, until the fragment subgraphs are sufficiently small. Our tests on three widely used protein-protein interaction data sets and comparisons with several latest methods for protein complex identification demonstrate the strong performance of our method in predicting novel protein complexes in terms of its specificity and efficiency. Given the high specificity (or precision) that our method has achieved, we conjecture that our prediction results imply more than 200 novel protein complexes.
Feng
Jianxing
J
Department of Computer Science and Technology, Tsinghua University, 1207B Zijing Building 15#, Beijing 100084, China. fengjx06@mails.tsinghua.edu.cn
Jiang
Rui
R
Jiang
Tao
T
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D020869:Gene Expression Profiling / Q000379:methods*; D040081:Protein Array Analysis; D025941:Protein Interaction Mapping / Q000379:methods*; D015203:Reproducibility of Results; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism
D029701:Saccharomyces cerevisiae Proteins