A simple method for inferring strengths of protein-protein interactions

Various computational methods have been proposed for inference of protein-protein interactions since protein-protein interaction plays an essential role in many cellular processes. One of well-studied approaches is to infer protein-protein interactions based on domain-domain interactions. To extend this approach, we proposed a method called LPNM to infer ratios of interactions, which outperformed other existing methods in terms of error of predicted ratios. However, since the LPNM method is based on the linear programming approach, it may require a large amount of time to infer interactions for a large data set. In this paper, we propose a simple method to infer the ratios of protein-protein interactions based on the association method by Sprinzak et al. In an experiment with a data set of protein-protein interactions in yeast, it runs more than 150 times as fast as the LPNM method, and achieves almost the same accuracy. On implementing algorithms for the inference problem, it is essential to understand how difficult the problem is. Even though various methods for the problem have been already proposed, it has not been analyzed rigorously from a computational point of view. We hence define a problem to maximize correctly classified examples, and prove the problem is MAX SNP-hard, which also means the problem is NP-hard.