TY - GEN
T1 - Quasi-bicliques
T2 - 14th Annual International Conference on Computing and Combinatorics (COCOON 2008)
AU - Liu, Xiaowen
AU - Li, Jinyan
AU - Wang, Lusheng
PY - 2008
Y1 - 2008
N2 - Protein-protein interactions (PPIs) are one of the most important mechanisms in cellular processes. To model protein interaction sites, recent studies have suggested to find interacting protein group pairs from large PPI networks at the first step, and then to search conserved motifs within the protein groups to form interacting motif pairs. To consider noise effect and incompleteness of biological data, we propose to use quasi-bicliques for finding interacting protein group pairs. We investigate two new problems which arise from finding interacting protein group pairs: the maximum vertex quasi-biclique problem and the maximum balanced quasi-biclique problem. We prove that both problems are NP-hard. This is a surprising result as the widely known maximum vertex biclique problem is polynomial time solvable [16]. We then propose a heuristic algorithm which uses the greedy method to find the quasi-bicliques from PPI networks. Our experiment results on real data show that this algorithm has a better performance than a benchmark algorithm for identifying highly matched BLOCKS and PRINTS motifs. © 2008 Springer-Verlag Berlin Heidelberg.
AB - Protein-protein interactions (PPIs) are one of the most important mechanisms in cellular processes. To model protein interaction sites, recent studies have suggested to find interacting protein group pairs from large PPI networks at the first step, and then to search conserved motifs within the protein groups to form interacting motif pairs. To consider noise effect and incompleteness of biological data, we propose to use quasi-bicliques for finding interacting protein group pairs. We investigate two new problems which arise from finding interacting protein group pairs: the maximum vertex quasi-biclique problem and the maximum balanced quasi-biclique problem. We prove that both problems are NP-hard. This is a surprising result as the widely known maximum vertex biclique problem is polynomial time solvable [16]. We then propose a heuristic algorithm which uses the greedy method to find the quasi-bicliques from PPI networks. Our experiment results on real data show that this algorithm has a better performance than a benchmark algorithm for identifying highly matched BLOCKS and PRINTS motifs. © 2008 Springer-Verlag Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/48249103436
UR - https://www.scopus.com/pages/publications/48249103436#tab=impact
U2 - 10.1007/978-3-540-69733-6_26
DO - 10.1007/978-3-540-69733-6_26
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540697322
SN - 9783540697329
VL - 5092 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 255
EP - 264
BT - Computing and Combinatorics
PB - Springer Verlag
Y2 - 27 June 2008 through 29 June 2008
ER -