Pairwise versus multiple network alignment

Authors: 
Vipin Vijayan, Eric Krebs, Lei Meng, Tijana Milenkovic
Citation: 
Vipin Vijayan, Eric Krebs, and Tijana Milenkovic (2017), Pairwise versus multiple network alignment, arXiv:1709.04564 [q-bio.MN]
Publication Date: 
September, 2017

Network alignment (NA) can be pairwise (PNA) and multiple (MNA). PNA produces aligned node pairs between two networks. MNA produces aligned node clusters between more than two networks. Recently, the focus has shifted from PNA to MNA, because MNA captures conserved regions between more networks than PNA (and MNA is thus considered to be more insightful), though at higher computational complexity. The issue is that, due to the different outputs of PNA and MNA, a PNA method is only compared to other PNA methods, and an MNA method is only compared to other MNA methods. Comparison of PNA against MNA must be done to evaluate whether MNA's higher complexity is justified by its higher accuracy. We introduce a framework that allows for this. We compare PNA against MNA in both a pairwise (native to PNA) and multiple (native to MNA) manner. Shockingly, we find that PNA is more accurate and faster than MNA in both cases. This result might guide future research efforts in the NA field.