GASOLINE: a Greedy And Stochastic algorithm for Optimal Local multiple alignment of Interaction NEtworks

The analysis of structure and dynamics of biological networks plays a central role in understanding the intrinsic complexityof biological systems. Biological networks have been considered a suitable formalism to extend evolutionary andcomparative biology. In this paper we present GASOLINE, an algorithm for multiple local network alignment based onstatistical iterative sampling in connection to a greedy strategy. GASOLINE overcomes the limits of current approaches byproducing biologically significant alignments within a feasible running time, even for very large input instances. Themethod has been extensively tested on a database of real and synthetic biological networks. A comprehensive comparisonwith state-of-the art algorithms clearly shows that GASOLINE yields the best results in terms of both reliability of alignmentsand running time on real biological networks and results comparable in terms of quality of alignments on syntheticnetworks. GASOLINE has been developed in Java, and is available, along with all the computed alignments, at the followingURL: http://ferrolab.dmi.unict.it/gasoline/gasoline.html