Skip to main navigation Skip to search Skip to main content

Quasi-bicliques: Complexity and binding pairs

  • Xiaowen Liu
  • , Jinyan Li
  • , Lusheng Wang*
  • *Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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-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.
Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication14th Annual International Conference, COCOON 2008, Proceedings
PublisherSpringer Verlag
Pages255-264
Volume5092 LNCS
ISBN (Print)3540697322, 9783540697329
DOIs
Publication statusPublished - 2008
Event14th Annual International Conference on Computing and Combinatorics (COCOON 2008) - Dalian, China
Duration: 27 Jun 2008 → 29 Jun 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5092 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Annual International Conference on Computing and Combinatorics (COCOON 2008)
PlaceChina
CityDalian
Period27/06/08 → 29/06/08

Fingerprint

Dive into the research topics of 'Quasi-bicliques: Complexity and binding pairs'. Together they form a unique fingerprint.

Cite this