School of Computing

Message-passing algorithms for the prediction of protein domain interactions from protein�protein interaction data

Mudassar Iqbal, Alex A. Freitas, Colin G. Johnson, and Massimo Vergassola

Bioinformatics, 24(18):182-196, September 2008 [doi].

Abstract

Motivation: Cellular processes often hinge upon specific interactions among proteins, and knowledge of these processes at a system level constitutes a major goal of proteomics. In particular, a greater understanding of protein-protein interactions can be gained via a more detailed investigation of the protein domain interactions that mediate the interactions of proteins. Existing high-throughput experimental techniques assay protein-protein interactions, yet they do not provide any direct information on the interactions among domains. Inferences concerning the latter can be made by analysis of the domain composition of a set of proteins and their interaction map. This inference problem is non-trivial, however, due to the high level of noise generally present in experimental data concerning protein-protein interactions. This noise leads to contradictions, i.e. the impossibility of having a pattern of domain interactions compatible with the protein-protein interaction map.

Results: We formulate the problem of prediction of protein domain interactions in a form that lends itself to the application of belief propagation, a powerful algorithm for such inference problems, which is based on message passing. The input to our algorithm is an interaction map among a set of proteins, and a set of domain assignments to the relevant proteins. The output is a list of probabilities of interaction between each pair of domains. Our method is able to effectively cope with errors in the protein-protein interaction dataset and systematically resolve contradictions. We applied the method to a dataset concerning the budding yeast Saccharomyces cerevisiae and tested the quality of our predictions by cross-validation on this dataset, by comparison with existing computational predictions, and finally with experimentally available domain interactions. Results compare favourably to those by existing algorithms.

Availability: A C language implementation of the algorithm is available upon request.

Download publication 169 kbytes (PDF)

Bibtex Record

@article{2808,
author = {Mudassar Iqbal and Alex A. Freitas and Colin G. Johnson and Massimo Vergassola},
title = {Message-passing algorithms for the prediction of protein domain interactions from protein�protein interaction data},
month = {September},
year = {2008},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {10.1093/bioinformatics/btn366 },
url = {http://www.cs.kent.ac.uk/pubs/2008/2808},
    publication_type = {article},
    submission_id = {12753_1220878394},
    ISSN = {1460-2059},
    journal = {Bioinformatics},
    volume = {24},
    number = {18},
    publisher = {Oxford University Press},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014