Protein-Protein Interaction Networks Alignment using Mathematical Model Approximation

The optimal network alignment problem is an NP-hard problem. In this paper, in order to reduce the runtime of solving this problem, an approximated mathematical model is proposed. To be more precise, the similarity matrix of the two networks is used to reduce the number of model's variables. For this purpose, in the proposed approximation model, instead of checking the possibility of alignment of each protein in the first network with every protein in the second one, we only check the alignment of each protein in the first network to the few most similar ones in the second network. At last, in order to solve the proposed approximation model, the Active Set algorithm is used. This new method has been tested on real protein-protein interaction (PPI) networks of different real and synthetic species. Experimental results indicated improvements in the alignment precision of different networks especially large ones in comparison with NETwork ALigner (NETAL) algorithm and also tremendous reduction of running time in comparison with exact model. In addition, the proposed method could achieve desirable precision on synthetic protein-protein networks.