Modeling protein interacting groups by quasi-bicliques : Complexity, algorithm, and application
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Article number | 4540092 |
Pages (from-to) | 354-364 |
Journal / Publication | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
Volume | 7 |
Issue number | 2 |
Publication status | Published - 2010 |
Link(s)
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 the noise effect and the incompleteness of biological data, we propose to use quasi-bicliques for finding interacting protein group pairs. We investigate two new problems that 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 [1]. We then propose a heuristic algorithm that 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. We also report results of two case studies on interacting motif pairs that map well with two interacting domain pairs in iPfam. Availability: The software and supplementary information are available at http://www.cs.cityu.edu.hk/~lwang/software/ppi/index.html. © 2006 IEEE.
Research Area(s)
- Algorithms, Interaction sites, NP-hardness, PPI networks, Protein interacting groups, Protein interaction sites, Protein-protein interactions, Quasi-bicliques
Citation Format(s)
Modeling protein interacting groups by quasi-bicliques: Complexity, algorithm, and application. / Liu, Xiaowen; Li, Jinyan; Wang, Lusheng.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 7, No. 2, 4540092, 2010, p. 354-364.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 7, No. 2, 4540092, 2010, p. 354-364.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review