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.
- M. Koyuturk. Algorithmic
and analytical methods in network biology. WIREs Systems Biology
& Medicine, 2(3):277-292, 2010. pdf
- M. Koyuturk, Y. Kim, U. Topkara, S. Subramaniam, W. Szpankowski, and A. Grama,
Pairwise alignment of protein interaction networks,
Journal of Computational Biology,
13(2), 182-199, 2006.
- M. Koyuturk, A. Grama, and W. Szpankowski,
Pairwise local alignment of protein interaction networks guided by models