title: SLIDER: a generic metaheuristic for the discovery of correlated motifs in protein-protein interaction networks.
abstract: Correlated motif mining (cmm) is the problem of finding overrepresented pairs of patterns, called motifs, in sequences of interacting proteins. 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 generic metaheuristic slider which uses steepest ascent 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. The slider-implementation and the data used in the experiments are available on http://bioinformatics.uhasselt.be.
authors.affiliation: Hasselt University, Agoralaan Gebouw D, B-3590 Diepenbeek, Belgium. peter.boyen@uhasselt.be
authors.forename: Peter
authors.initials: P
authors.lastname: Boyen
authors.forename: Dries
authors.initials: D
authors.lastname: Van Dyck
authors.forename: Frank
authors.initials: F
authors.lastname: Neven
authors.forename: Roeland C H J
authors.initials: RC
authors.lastname: van Ham
authors.forename: Aalt D J
authors.initials: AD
authors.lastname: van Dijk
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D016009:Chi-Square Distribution; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D005656:Fungal Proteins / Q000737:chemistry; D006801:Humans; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps; D011506:Proteins / Q000737:chemistry*; D020539:Sequence Analysis, Protein
chemical_list: D005656:Fungal Proteins; D011506:Proteins