SLIDER: A Generic Metaheuristic for the Discovery of Correlated Motifs in Protein-Protein Interaction Networks

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.

Bibliographic Details

Main Authors:	Boyen, P., van Dyck, D., Neven, F., van Ham, R.C.H.J., van Dijk, A.D.J.
Format:	Article/Letter to editor biblioteca
Language:	English
Subjects:	pairs, scale, sequences,
Online Access:	https://research.wur.nl/en/publications/slider-a-generic-metaheuristic-for-the-discovery-of-correlated-mo
Tags:	Add Tag No Tags, Be the first to tag this record!