MaWISh: Software for Pairwise Alignment of Protein-Protein Interaction Networks

An important problem in network biology is to align protein-protein interaction networks of different species to understand the conservation and divergence of network mechanisms (pathways, protein complexes) etc. across different species. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. MaWISh (Maximum Weight Induced Subgraph) is a comprehensive alignment tool for PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. It is based on a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates the similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, it facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, MaWISh allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. MaWISh is implemented in C and is freely available as open source.