The alignment of biological networks enables to shed light on important biological information, such as evolutionarily conserved patterns for protein interaction networks. Alignment algorithms fall in two major classes: local and global. The local network alignment (LNA) aims to discover unique sub-regions of similarity among networks, while the global network alignment (GNA) aims to find large conserved regions by matching all the nodes of the input networks. Some recent works demonstrated that two approaches are complementary. Thus it is possible to combine them to improve the alignment performances. LNA algorithms need as input both networks and supplementary information to start the process. Such information is not available in all the contexts, such as for networks representing brain connections. In particular global alignment may be used to produce such information without any a priori knowledge about networks. We recently explored such possibility. Here, we here extend and refine our previous results by introducing SL-GLAlign (Simulated Annealing-Global Local Aligner), a novel framework methodology based on the use of topological information extracted from global alignment to guide the building of the local alignment. To assess our methodology, we tested SL-GLAlign on biological networks. Results confirm that SL-GLAlign methodology can build improved alignment when compared to the state-of-the-art local alignment algorithms.
Dataset