title: GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks.
abstract: The analysis of structure and dynamics of biological networks plays a central role in understanding the intrinsic complexity of biological systems. Biological networks have been considered a suitable formalism to extend evolutionary and comparative biology. In this paper we present GASOLINE, an algorithm for multiple local network alignment based on statistical iterative sampling in connection to a greedy strategy. GASOLINE overcomes the limits of current approaches by producing biologically significant alignments within a feasible running time, even for very large input instances. The method has been extensively tested on a database of real and synthetic biological networks. A comprehensive comparison with state-of-the art algorithms clearly shows that GASOLINE yields the best results in terms of both reliability of alignments and running time on real biological networks and results comparable in terms of quality of alignments on synthetic networks. GASOLINE has been developed in Java, and is available, along with all the computed alignments, at the following URL: http://ferrolab.dmi.unict.it/gasoline/gasoline.html.
authors.affiliation: Department of Computer Science, University of Pisa, Pisa, Italy.
authors.forename: Giovanni
authors.initials: G
authors.lastname: Micale
authors.affiliation: Department of Clinical and Molecular Biomedicine, University of Catania, Catania, Italy.
authors.forename: Alfredo
authors.initials: A
authors.lastname: Pulvirenti
authors.affiliation: Department of Clinical and Molecular Biomedicine, University of Catania, Catania, Italy.
authors.forename: Rosalba
authors.initials: R
authors.lastname: Giugno
authors.affiliation: Department of Clinical and Molecular Biomedicine, University of Catania, Catania, Italy.
authors.forename: Alfredo
authors.initials: A
authors.lastname: Ferro
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D051379:Mice; D025941:Protein Interaction Mapping / Q000379:methods*; D013269:Stochastic Processes; D013997:Time Factors