Searching maximum quasi-bicliques from protein-protein interaction network


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.

Share and Cite:

Liu, H. , Liu, J. and Wang, L. (2008) Searching maximum quasi-bicliques from protein-protein interaction network. Journal of Biomedical Science and Engineering, 1, 200-203. doi: 10.4236/jbise.2008.13034.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Fields S. and Sternglanz R. (1994) The two-hybrid system: an assay for protein-protein interactions, Trends Genet, 10(8), 286-292.
[2] 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.
[3] 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.
[4] Garey M. R., Johnson D. S., et al.( 1976) Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3): 237-267.
[5] Karp R. M. (1972) Reducibility among combinatorial problems, Complexity of Computer Computations, 43, 85-103.
[6] Even S. and Shiloach Y. (1975) NP-completeness of several ar-rangement problems, Dept. Computer Science, Technion, Haifa, Is-rael, Tech. Rep, 43.
[7] 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.
[8] Grotschel M. and Pulleyblank W. R. (1981) Weakly bipartite graphs and the max-cut problem, Operations Research Letters, 1(23-27), 482.
[9] Barahona F. (1983) On some weakly bipartite graphs, Operations Research Letters, 5: 239242.
[10] Hopfield J. J. and Tank D. W. (1985) "Neural" computation of deci-sions in optimization problems, Biological Cybernetics, 52(3), 141-152.
[11] 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.
[12] 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.
[13] 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.
[14] Przulj N., (2004) Graph theory approaches to protein interaction data analysis, in Knowledge Discovery in High-Throughput Bio-logical Domains, Interpharm/CRC.
[15] von Mering C., Krause R., et al. (2002) Comparative assessment of large-scale data sets of protein-protein interactions, Nature, 417(6887), 399-403.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.