title: APPAGATO: an APproximate PArallel and stochastic GrAph querying TOol for biological networks.
abstract: Biological network querying is a problem requiring a considerable computational effort to be solved. Given a target and a query network, it aims to find occurrences of the query in the target by considering topological and node similarities (i.e. mismatches between nodes, edges, or node labels). Querying tools that deal with similarities are crucial in biological network analysis because they provide meaningful results also in case of noisy data. In addition, as the size of available networks increases steadily, existing algorithms and tools are becoming unsuitable. This is rising new challenges for the design of more efficient and accurate solutions.
  
  
  
  This paper presents APPAGATO, a stochastic and parallel algorithm to find approximate occurrences of a query network in biological networks. APPAGATO handles node, edge and node label mismatches. Thanks to its randomic and parallel nature, it applies to large networks and, compared with existing tools, it provides higher performance as well as statistically significant more accurate results. Tests have been performed on protein-protein interaction networks annotated with synthetic and real gene ontology terms. Case studies have been done by querying protein complexes among different species and tissues.
  
  
  
  APPAGATO has been developed on top of CUDA-C ++ Toolkit 7.0 framework. The software is available online http://profs.sci.univr.it/∼bombieri/APPAGATO CONTACT: rosalba.giugno@univr.it
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science, University of Verona, Strada Le Grazie 15 - 37134, Verona.
authors.forename: Vincenzo
authors.initials: V
authors.lastname: Bonnici
authors.affiliation: Department of Computer Science, University of Verona, Strada Le Grazie 15 - 37134, Verona.
authors.forename: Federico
authors.initials: F
authors.lastname: Busato
authors.affiliation: Department of Math and Computer Science, University of Catania, Viale a. Doria 6 - 95125, Catania.
authors.forename: Giovanni
authors.initials: G
authors.lastname: Micale
authors.affiliation: Department of Computer Science, University of Verona, Strada Le Grazie 15 - 37134, Verona.
authors.forename: Nicola
authors.initials: N
authors.lastname: Bombieri
authors.affiliation: Department of Clinical and Experimental Medicine, University of Catania, via Palermo, 636 - 95122, Catania.
authors.forename: Alfredo
authors.initials: A
authors.lastname: Pulvirenti
authors.affiliation: Department of Computer Science, University of Verona, Strada Le Grazie 15 - 37134, Verona Department of Clinical and Experimental Medicine, University of Catania, via Palermo, 636 - 95122, Catania.
authors.forename: Rosalba
authors.initials: R
authors.lastname: Giugno
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D063990:Gene Ontology; D006801:Humans; D060066:Protein Interaction Maps; D012984:Software