GLAlign: A Novel Algorithm for Local Network Alignment

Networks are successfully used as a modelling framework in many application domains. For instance, Protein-Protein Interaction Networks (PPINs) model the set of interactions among proteins in a cell. A critical application of network analysis is the comparison among PPINs of different organisms to reveal similarities among the underlying biological processes. Algorithms for comparing networks (also referred to as network aligners) fall into two main classes: global aligners, which aim to compare two networks on a global scale, and local aligners that evidence single sub-regions of similarity among networks. The possibility to improve the performance of the aligners by mixing the two approaches is a growing research area. In our previous work, we started to explore the possibility to use global alignment to improve the local one. We here examine further this possibility by using topological information extracted from global alignment to guide the steps of the local alignment. Therefore, we present GLAlign (Global Local Aligner), a methodology that improves the performances of local network aligners by exploiting a preliminary global alignment. Furthermore, we provide an implementation of GLAlign. As a proof-of-principle, we evaluated the performance of the GLAlign prototype. Results show that GLAlign methodology outperforms the state-of-the-art local alignment algorithms. GLAlign is publicly available for academic use and can be downloaded here: https://sites.google.com/site/globallocalalignment/.