Belief Propagation Estimation of Protein and Domain Interactions using the Sum-Product Algorithm

Faruck Morcos, Marcin Sikora, Mark S. Alber, Dale Kaiser, and Jesús A. Izaguirre
Information Theory, IEEE Transactions on 56.2 (2010): 742-755.
Publication Date: 
February, 2010

In this paper, a novel framework is presented to estimate protein–protein interactions (PPIs) and domain–domain interactions (DDIs) based on a belief propagation estimation method that efficiently computes interaction probabilities. Experimental interactions, domain architecture, and gene ontology (GO) annotations are used to create a factor graph representation of the joint probability distribution of pairwise protein and domain interactions. Bound structures are used as a priori evidence of domain interactions. These structures come from experiments documented in iPfam. The probability distribution contained in the factor graph is then efficiently marginalized with a message passing algorithm called the sum–product algorithm (SPA). This method is compared against two other approaches: maximum-likelihood estimation (MLE) and maximum specificity set cover (MSSC). SPA performs better for simulated scenarios and for inferring high-quality PPI data of Saccharomyces cerevisiae. This framework can be used to predict potential protein and domain interactions at a genome wide scale and for any organism with identified protein–domain architectures.