Protein interaction inference as a Max-SAT problem

Ya Zhang, Hongyuan Zha, Chao Hisen Chu, Xiang Ji

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Discovering interacting proteins is essential for understanding protein functions. However, high throughput interaction data are inherently noisy and only cover a small portion of the whole interactome. Domains, the building block of proteins, are believed to be responsible for the interactions among proteins. An abstract representation of interactome is achieved at domain level and this representation also facilitates the discovery of unobserved protein-protein interactions. Many domain-based approaches have been proposed to predict protein-protein interactions and promising results have been obtained. Existing methods generally assume that domain interactions are independent of each other for the convenience of computational modeling. In this paper, a new framework of learning is proposed. The framework makes no assumption about domain interactions and consider protein interactions resulting from multiple domain interactions which may be dependent of each other. With a conjunctive normal form representation of the relationship between protein interactions and domain interactions, the problem of interaction inference is modeled as a constraint satisfiability problem and solved via linear programming. Experimental results on a combined yeast data set have demonstrated the robustness of and the accuracy of the proposed algorithm.

Original languageEnglish (US)
Title of host publication2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 - Workshops
PublisherIEEE Computer Society
ISBN (Electronic)0769526608
DOIs
StatePublished - 2005
Event2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 - Workshops - San Diego, United States
Duration: Sep 21 2005Sep 23 2005

Publication series

NameIEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops
Volume2005-September
ISSN (Print)2160-7508
ISSN (Electronic)2160-7516

Conference

Conference2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 - Workshops
Country/TerritoryUnited States
CitySan Diego
Period9/21/059/23/05

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Protein interaction inference as a Max-SAT problem'. Together they form a unique fingerprint.

Cite this