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.

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

GIUGNO, ROSALBA;
2014-01-01

Abstract

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.
2014
network analysis
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/940430
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 20
social impact