Systems biology Advance Access publication September 17, 2013 Optimizing a 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 identify-ing functional orthologs. Furthermore, it can provide useful insights into the species ’ evolution. Results: We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effective-ness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology infor-mation, trading it off for sequence information. In practice, our algo-rithm 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 flexible 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 Web site