Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/12110
Title: SLIDER: A Generic Metaheuristic for the Discovery of Correlated Motifs in Protein-Protein Interaction Networks
Authors: BOYEN, Peter 
VAN DYCK, Dries 
NEVEN, Frank 
van Ham, Roeland C. H. J.
van Dijk, Aalt D. J.
Issue Date: 2011
Publisher: IEEE COMPUTER SOC
Source: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 8(5). p. 1344-1357
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.
Notes: [Boyen, P; Van Dyck, D; Neven, F] Hasselt Univ, B-3590 Diepenbeek, Belgium [Boyen, P; Van Dyck, D; Neven, F] Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium [van Dijk, ADJ] Wageningen Univ & Res Ctr, Bioinformat Grp, NL-6708 PB Wageningen, Netherlands peter.boyen@uhasselt.be; dries.vandyck@uhasselt.be; frank.neven@uhasselt.be; roeland.vanham@wur.nl; aaltjan.vandijk@wur.nl
Keywords: Graphs and networks; biology and genetics
Document URI: http://hdl.handle.net/1942/12110
ISSN: 1545-5963
e-ISSN: 1557-9964
DOI: 10.1109/TCBB.2011.17
ISI #: 000292681800016
Category: A1
Type: Journal Contribution
Validations: ecoom 2012
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
preprint.pdfPreprint1.2 MBAdobe PDFView/Open
Show full item record

Google ScholarTM

Check

Altmetric


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