Quasi-bicliques: Complezity and Binding Pairs

摘要：

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 quasibiclique problem and the maximum balanced quasibiclique problem. We prove that both problems are NPhard. This is a surprising result as the widely known maximum vertex biclique problem is polynomial time

作者: Xiaowen Liu Jinyan Li Lusheng Wang

作者单位: Department of Computer Science,City University of Hong Kong,Kowloon, Hong Kong Department of Compute School of Computer Engineering,Nanyang Technological University, Singapore 639798 Department of Computer Science,City University of Hong Kong, Kowloon, Hong Kong

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 255-264

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）