Protein interactions typically arise from a physical interaction of one or
more small sites on the surface of the two proteins. Identifying these sites
is very important for drug and protein design. In this paper, we propose a
computational method based on probabilistic relational model that attempts
to address this task using high-throughput protein interaction data and a
set of short sequence motifs. We learn the model using the EM algorithm,
with a branch-and-bound algorithm as an approximate inference for the
E-step. Our method searches for motifs whose presence in a pair of
interacting proteins can explain their observed interaction. It also tries
to determine which motif pairs have high affinity, and can therefore lead to
an interaction. We show that our method is more accurate than others at
predicting new protein-protein interactions. More importantly, by examining
solved structures of protein complexes, we find that 2/3 of the predicted
active motifs correspond to actual interaction sites.