Inferring Protein-Protein Interactions by Combinatorial Models

identifying interacting proteins is essential for understanding protein functions and biological signal transduction pathways. Domains as basic components of a protein are believed to be responsible for the physical interaction of a pair of proteins. Most of existing methods based on domain information are probabilistic and assume that domain interactions are independent. In this paper, we propose a new framework based on a deterministic model to infer protein interactions. The model employs a parsimony principle, i.e., the observed protein interactions are contributed by as few as possible different interacting domain pairs. It can be formulated as an integer linear programming which is in turn solved by its linear programming relaxation. We use real protein interaction data to verify our model and algorithm. Experiment results show the effectiveness of the proposed model and algorithm and demonstrate that such a parsimony principle can achieve the prediction accuracy comparable to that of maximum likelihood method.