IsoRank & IsoRankN
massachusetts institute of technology (mit)
computer science and artificial intelligence laboratory (csail)
theory of computation group (toc)

computation and biology group (compbio)

email queries Bonnie Berger or

IsoRank (2008)

We describe an algorithm for global alignment of multiple protein-protein inter- action (PPI) networks. The algorithm aims to maximize the overall match across all input networks. This is, to our knowledge, the first algorithm for this problem. In contrast, much of the previous work in the field has focused on local network alignment. The intuition behind our algorithm is that a protein in one PPI net- work is a good match for a protein in another network if the former's neighbors are good matches for the latter's neighbors. We encode this intuition by constructing an eigenvalue problem for every pair of input networks and then using k-partite matching to extract the final global alignment across all the species. Using our algorithm we compute the first known global alignment of PPI networks from five species: yeast, fly, worm, mouse and human. The global alignment immediately suggests functional orthologs across these species; we believe these are the first set of functional orthologs that cover all the five species. We show that these functional orthologs compare favorably with current sequence-only orthology prediction approaches, including better prediction of orthologs for some human disease-related proteins.

If you use IsoRank, please cite this paper:
Rohit Singh, Jinbo Xu, and Bonnie Berger. (2008) Global alignment of multiple protein interaction networks with application to functional orthology detection, Proc. Natl. Acad. Sci. USA, 105:12763-12768. (Supplementary Information)

IsoRankN (2009)

We describe IsoRankN (IsoRank-Nibble), a global multiple-network alignment tool based on spectral clustering on the induced graph of pairwise alignment scores. IsoRankN outperforms existing algorithms for global network alignment in coverage and consistency on multiple alignments of the five available eukaryotic networks. Being based on spectral methods, IsoRankN is both error-tolerant and computationally efficient.

Our software is available freely for non-commercial purposes.

IsoRankn 64-bit Linux executable (see above for data)
IsoRankn 32-bit Linux executable (see above for data)

If you use IsoRankN, please cite this paper:
Chung-Shou Liao, Kanghao Lu, Michael Baym, Rohit Singh, and Bonnie Berger. (2009) IsoRankN: Spectral methods for global alignment of multiple protein networks, Bioinformatics, 25:i253-i258.