spinal

Overview We provide the SPINAL algorithm for the problem of globally aligning a pair of PPI networks. Our algorithm proceeds in two phases. In the first coarse-grained alignment phase we construct all pairwise initial similarity scores based on pairwise local neighborhood matchings. Employing the produced similarity scores, the fine-grained alignment phase produces the final one-to-one mapping by iteratively growing a locally improved solution subset. Both phases make use of the construction of "neighborhood bipartite graphs" and the "contributors" as a common primitive. We assess the performance of our algorithm on the PPI networks of yeast, fly, human, and worm. We show that based on the accuracy measures employed in relevant work, our method outperforms the state-of-the-art algorithms. Furthermore our algorithm does not suffer from scalability issues, as such accurate results are achieved in reasonable running times as compared to the benchmark a