A novel ant based algorithm for multiple graph alignment

Multiple graph alignment (MGA) is a new approach to analyze protein structure in order to exploring their functional similarity. In this article, we propose a two-stage memetic algorithm to solve the MGA problem, named ACO-MGA2, based on ant colony optimization metaheuristic. A local search procedure is applied only to the second stage of the algorithm to save runtime. Experimental results have shown that ACO-MGA2 outperforms state-of-the-art algorithms while producing alignments of better quality.