Paper Info
Title
Quasi-bicliques: Complexity and Binding Pairs
Abstract
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-bicliquesfor 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.
Year
DOI
Venue
2008
10.1007/978-3-540-69733-6_26
COCOON
Keywords
Field
DocType
interacting motif pair,interacting protein group pair,maximum balanced quasi-biclique problem,binding pairs,protein group,maximum vertex biclique problem,model protein interaction site,new problem,maximum vertex quasi-biclique problem,benchmark algorithm,heuristic algorithm,polynomial time,protein protein interaction,biological data
Discrete mathematics,Biological data,Complete bipartite graph,Combinatorics,Vertex (geometry),Computer science,Heuristic (computer science),Bipartite graph,Greedy algorithm,Time complexity
Conference
Volume
ISSN
Citations 
5092
0302-9743
5
PageRank 
References 
Authors
0.44
8
3
Name
Order
Citations
PageRank
Xiaowen Liu1886.51
jinyan li22404191.25
Lusheng Wang32433224.97