Research ArticleOpen AccessGoogle Scholar indexed
Searching maximum quasi-bicliques from protein-protein interaction network
School of Computer, Wuhan University, Wuhan 430079, China
School of Computer, Wuhan University, Wuhan 430079, China
School of Computer, Wuhan University, Wuhan 430079, China
- 1 School of Computer, Wuhan University, Wuhan 430079, China
- 2 School of Computer, Wuhan University, Wuhan 430079, China
- 3 School of Computer, Wuhan University, Wuhan 430079, China
Journal of Biomedical Science and Engineering·Volume 01 (2008)·Pages 200–203·Published 15 October 2008·DOI10.4236/jbise.2008.13034
Copy link · social · email
Abstract
Searching the maximum bicliques or bipartite subgraphs in a graph is a tough question. We proposed a new and efficient method, Searching Quasi-Bicliques (SQB) algorithm, to detect maximum quasi-bicliques from protein-protein interaction network. As a Divide-and-Conquer method, SQB consists of three steps: first, it divides the protein-protein interaction network into a number of Distance-2-Subgraphs; second, by combining top-down and branch-and-bound methods, SQB seeks quasi-bicliques from every Distance-2-Subgraph; third, all the redundant results are removed. We successfully applied our method on the Saccharomyces cerevisiae dataset and obtained 2754 distinct quasi-bicliques.
KeywordsSearching Quasi-Bicliques algorithmQuasi-bicliqueProtein-Protein Interaction NetworkDistance-2-SubgraphDi-vide-and-Conquer method
- Fields S. and Sternglanz R. (1994) The two-hybrid system: an assay for protein-protein interactions, Trends Genet, 10(8), 286-292.
- Bauer A. and Kuster B. (2003) Affinity purification-mass spec-trometry. Powerful tools for the characterization of protein com-plexes, Eur J Biochem, 270(4), 570-578.
- Tong A. H., Drees B., et al.( 2002) A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules, Science, 295(5553), 321-324.
- Garey M. R., Johnson D. S., et al.( 1976) Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3): 237-267.
- Karp R. M. (1972) Reducibility among combinatorial problems, Complexity of Computer Computations, 43, 85-103.
- Even S. and Shiloach Y. (1975) NP-completeness of several ar-rangement problems, Dept. Computer Science, Technion, Haifa, Is-rael, Tech. Rep, 43.
- Bondy J. A. and Locke S. C. (1986) Largest bipartite subgraphs in triangle-free graphs with maximum degree three, Journal of graph theory, 10(4), 477-504.
- Grotschel M. and Pulleyblank W. R. (1981) Weakly bipartite graphs and the max-cut problem, Operations Research Letters, 1(23-27), 482.
- Barahona F. (1983) On some weakly bipartite graphs, Operations Research Letters, 5: 239242.
- Hopfield J. J. and Tank D. W. (1985) "Neural" computation of deci-sions in optimization problems, Biological Cybernetics, 52(3), 141-152.
- Hopfield J. J. (1984) Neurons with Graded Response Have Collec-tive Computational Properties like Those of Two-State Neurons, Proceedings of the National Academy of Sciences of the United States of America, 81(10), 3088-3092.
- Li H., Li J., et al.( 2006) Discovering motif pairs at interaction sites from protein sequences on a proteome-wide scale, Bioinformatics, 22(8), 989-996.
- Agrawal R. and Srikant R. (1994) Fast Algorithms for Mining Asso-ciation Rules in Large Databases, Proceedings of the 20th Interna-tional Conference on Very Large Data Bases, 487-499.
- Przulj N., (2004) Graph theory approaches to protein interaction data analysis, in Knowledge Discovery in High-Throughput Bio-logical Domains, Interpharm/CRC.
- von Mering C., Krause R., et al. (2002) Comparative assessment of large-scale data sets of protein-protein interactions, Nature, 417(6887), 399-403.