Belief Propagation Estimation of Protein and Domain Interactions Using the Sum–Product Algorithm

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.