Alignment of protein interaction networks by integer quadratic programming

Abstract

With more and more data on protein-protein interaction (PPI) network available, the discovery of conserved patterns in these networks becomes an increasingly important problem. In this paper, to find the conserved substructures, we develop an efficient algorithm for aligning PPI networks based on both the protein sequence similarity and the network architecture similarity, by using integer quadratic programming (IQP). Such an IQP can be relaxed into the corresponding quadratic programming (QP) which in the case of biological data sets almost always ensures the integer solution. Therefore, a QP algorithm can be adopted to efficiently solve this IQP with out any approximation, thereby making PPI network alignment tractable. From the viewpoint of graph theory, the proposed method can identify similar subsets between two graphs, which allow gaps for nodes and edges.