Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9865
Title: SLIDER: Mining correlated motifs in protein-protein interaction networks
Authors: BOYEN, Peter 
NEVEN, Frank 
VAN DYCK, Dries 
van Dijk, Aalt D.J.
van Ham, Roeland C.H.J.
Issue Date: 2009
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 neigborhood 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.
Keywords: correlated motifs; PPI networks; local search
Document URI: http://hdl.handle.net/1942/9865
Category: R2
Type: Research Report
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
Slider tech report.pdf323.21 kBAdobe PDFView/Open
Show full item record

Page view(s)

82
checked on May 20, 2022

Download(s)

134
checked on May 20, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.