Discovery of motif pairs from protein-protein interaction networks

Motif pairs can provide insight on how protein-protein interactions are encoded. Their discovery requires laborious and expensive biological experiments. Recently, Tan et al. proposed a computational approach to find motif pairs in the sequences of interacting proteins. However, their approach suffers from two drawbacks. The heuristic used in their approach is not accurate and may lead to a result including some false positive motif instances. Their approach is also not scalable. It may take days to process a set of 5000 protein sequences with about 20,000 interactions. We present in this work a new algorithm DMPCP, which finds motifs from a subset of proteins and then pairs them up according to Chi-squared scoring functions. Experiments on real biological datasets and simulated datasets show that our approach is efficient and can find actual motif pairs. We also evaluated our approach on simulated datasets with planted motif pairs. The results show that our approach can achieve high success rates when interaction data is insufficient.