JBiSE  Vol.1 No.3 , November 2008
Searching maximum quasi-bicliques from protein-protein interaction network
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.
Cite this paper: nullLiu, 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.

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