Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 445885
Title Mining minimal motif pair sets maximally covering interactions in a protein-protein interaction network
Author(s) Boyen, P.; Neven, F.; Valentim, F.L.; Dijk, A.D.J. van
Source IEEE/ACM Transactions on Computational Biology and Bioinformatics 10 (2013)1. - ISSN 1545-5963 - p. 73 - 86.
DOI http://dx.doi.org/10.1109/TCBB.2012.165
Department(s) Laboratory of Molecular Biology
Biometris (WU MAT)
PRI BIOS Applied Bioinformatics
Publication type Refereed Article in a scientific journal
Publication year 2013
Keyword(s) interaction sites - high-throughput - binding-sites - prediction - database - hardness
Abstract Correlated motif covering (CMC) is the problem of finding a set of motif pairs, i.e., pairs of patterns, in the sequences of proteins from a protein-protein interaction network (PPI-network) that describe the interactions in the network as concisely as possible. In other words, a perfect solution for CMC would be a minimal set of motif pairs that describes the interaction behavior perfectly in the sense that two proteins from the network interact if and only if their sequences match a motif pair in the minimal set. In this paper, we introduce and formally define CMC and show that it is closely related to the red-blue set cover (RBSC) problem and its weighted version (WRBSC)--both well-known NP-hard problems for that there exist several algorithms with known approximation factor guarantees. We prove the hardness of approximation of CMC by providing an approximation factor preserving reduction from RBSC to CMC. We show the existence of a theoretical approximation algorithm for CMC by providing an approximation factor preserving reduction from CMC to WRBSC. We adapt the latter algorithm into a functional heuristic for CMC, called CMC-approx, and experimentally assess its performance and biological relevance. The implementation in Java can be found at >http://bioinformatics.uhasselt.be
Comments
There are no comments yet. You can post the first one!
Post a comment
 
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.