On the Structure and Efficient Computation of IsoRank Node Similarities.

The alignment of protein-protein interaction (PPI) networks has manyapplications, such as the detection of conserved biological network motifs, theprediction of protein interactions, and the reconstruction of phylogenetictrees [1, 2, 3]. IsoRank is one of the first global network alignmentalgorithms [4, 5, 6], where the goal is to match all (or most) of the nodes oftwo PPI networks. The IsoRank algorithm first computes a pairwise nodesimilarity metric, and then generates a matching between the two node setsbased on this metric. The metric is a convex combination of a structuralsimilarity score (with weight $ \alpha $) and an extraneous amino-acid sequencesimilarity score for two proteins (with weight $ 1 - \alpha $). In this shortpaper, we make two contributions. First, we show that when IsoRank similaritydepends only on network structure ($\alpha = 1$), the similarity of two nodesis only a function of their degrees. In other words, IsoRank similarity isinvariant to any network rewiring that does not affect the node degrees. Thisresult suggests a reason for the poor performance of IsoRank in structure-only($ \alpha = 1 $) alignment. Second, using ideas from [7, 8], we develop anapproximation algorithm that outperforms IsoRank (including recent versionswith better scaling, e.g., [9]) by several orders of magnitude in time andmemory complexity, despite only a negligible loss in precision.