Local optimization for global alignment of protein interaction networks

Motivation: The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species, and iden-tifying functional orthologs. Furthermore, it can provide useful insights into the species ’ evolution. Results: We propose a novel algorithm, PISwap, for optimizing glo-bal pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effec-tiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then itera-tively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexi-ble nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species. Availability: Our software is freely available for non-commercial purposes from our website