Identification of Protein Complexes from Tandem Affinity Purification/Mass Spectrometry Data via Biased Random Walk

Bingjing Cai, Haiying Wang, Huiru Zheng, Hui Wang

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Systematic identification of protein complexes from protein-protein interaction networks (PPIs) is an important application of data mining in life science. Over the past decades, various new clustering techniques have been developed based on modelling PPIs as binary relations. Non-binary information of co-complex relations (prey/bait) in PPIs data derived from tandem affinity purification/mass spectrometry (TAP-MS) experiments has been unfairly disregarded. In this paper, we propose a Biased Random Walk based algorithm for detecting protein complexes from TAP-MS data, resulting in the random walk with restarting baits (RWRB). RWRB is developed based on Random walk with restart. The main contribution of RWRB is the incorporation of co-complex relations in TAP-MS PPI networks into the clustering process, by implementing a new restarting strategy during the process of random walk. Through experimentation on un-weighted and weighted TAP-MS data sets, we validated biological significance of our results by mapping them to manually curated complexes. Results showed that, by incorporating non-binary, co-membership information, significant improvement has been achieved in terms of both statistical measurements and biological relevance. Better accuracy demonstrates that the proposed method outperformed several state-of-the-art clustering algorithms for the detection of protein complexes in TAP-MS data.
Original languageEnglish
Pages (from-to)455-466
Number of pages12
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number2
Early online date7 Sept 2014
Publication statusPublished (in print/issue) - 3 Apr 2015


  • Protein-protein interaction network
  • tandem affinity purification/mass spectrometry
  • protein complexes
  • random walk with restart


Dive into the research topics of 'Identification of Protein Complexes from Tandem Affinity Purification/Mass Spectrometry Data via Biased Random Walk'. Together they form a unique fingerprint.

Cite this