Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15428
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBOYEN, Peter-
dc.contributor.authorNEVEN, Frank-
dc.contributor.authorVAN DYCK, Dries-
dc.contributor.authorValentim, Felipe L.-
dc.contributor.authorvan Dijk, Aalt D. J.-
dc.date.accessioned2013-08-21T09:52:34Z-
dc.date.available2013-08-21T09:52:34Z-
dc.date.issued2013-
dc.identifier.citationIEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 10 (1), p. 73-86-
dc.identifier.issn1545-5963-
dc.identifier.urihttp://hdl.handle.net/1942/15428-
dc.description.abstractCorrelated 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.-
dc.description.sponsorshipResearch for this work was funded by the PhD grant of the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen). Aalt D.J. van Dijk was supported by the (Netherlands Organization for Scientific Research) VENI grant (863.08.027). Felipe L. Valentim was supported by the SYSFLO Marie Curie Initial Training Network.-
dc.language.isoen-
dc.publisherIEEE COMPUTER SOC-
dc.subject.otherGraphs and networks; biology and genetics; correlated motifs; PPI networks; local search-
dc.subject.otherBiochemical Research Methods; Computer Science, Interdisciplinary Applications; Mathematics, Interdisciplinary Applications; Statistics & Probability-
dc.titleMining Minimal Motif Pair Sets Maximally Covering Interactions in a Protein-Protein Interaction Network-
dc.typeJournal Contribution-
dc.identifier.epage86-
dc.identifier.issue1-
dc.identifier.spage73-
dc.identifier.volume10-
local.format.pages14-
local.bibliographicCitation.jcatA1-
dc.description.notesBoyen, P (reprint author), Hasselt Univ, B-3590 Diepenbeek, Belgium. Transnat Univ Limburg, B-3590 Diepenbeek, Belgium. Belgian Nucl Res Ctr SCK CEN, B-2400 Mol, Belgium. Plant Res Int, Appl Bioinformat, NL-6708 PB Wageningen, Netherlands. peter.boyen@uhasselt.be-
local.publisher.placeLOS ALAMITOS-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.identifier.doi10.1109/TCBB.2012.165-
dc.identifier.isi000319477300008-
item.accessRightsClosed Access-
item.fulltextNo Fulltext-
item.validationecoom 2014-
item.contributorBOYEN, Peter-
item.contributorNEVEN, Frank-
item.contributorVAN DYCK, Dries-
item.contributorValentim, Felipe L.-
item.contributorvan Dijk, Aalt D. J.-
item.fullcitationBOYEN, Peter; NEVEN, Frank; VAN DYCK, Dries; Valentim, Felipe L. & van Dijk, Aalt D. J. (2013) Mining Minimal Motif Pair Sets Maximally Covering Interactions in a Protein-Protein Interaction Network. In: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 10 (1), p. 73-86.-
crisitem.journal.issn1545-5963-
crisitem.journal.eissn1557-9964-
Appears in Collections:Research publications
Show simple item record

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

2
checked on Mar 29, 2024

Page view(s)

70
checked on Sep 6, 2022

Google ScholarTM

Check

Altmetric


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