SLIDER: Mining correlated motifs in protein-protein interaction networks

P. Boyen, A.D.J. van Dijk, R.C.H.J. van Ham, F. Neven

Research output: Contribution to conferenceConference paperAcademic

5 Citations (Scopus)

Abstract

Abstract—Correlated motif mining (CMM) is the problem to find overrepresented pairs of patterns, called motif pairs, in interacting protein sequences. Algorithmic solutions for CMM thereby provide a computational method for predicting binding sites for protein interaction. In this paper, we adopt a motif-driven approach where the support of candidate motif pairs is evaluated in the network. We experimentally establish the superiority of the Chi-square-based support measure over other support measures. Furthermore, we obtain that CMM is an NP-hard problem for a large class of support measures (including Chi-square) and reformulate the search for correlated motifs as a combinatorial optimization problem. We then present the method SLIDER which uses local search with a neighborhood function based on sliding motifs and employs the Chi-square-based support measure. We show that SLIDER outperforms existing motif-driven CMM methods and scales to large protein-protein interaction networks.
Original languageEnglish
Publication statusPublished - 2009
EventIEE International Conference on Data Mining (ICDM 2009), Miami, Florida, USA -
Duration: 6 Dec 20099 Dec 2009

Conference

ConferenceIEE International Conference on Data Mining (ICDM 2009), Miami, Florida, USA
Period6/12/099/12/09

Fingerprint Dive into the research topics of 'SLIDER: Mining correlated motifs in protein-protein interaction networks'. Together they form a unique fingerprint.

Cite this