{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T00:28:47Z","timestamp":1722731327967},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2016,4,29]],"date-time":"2016-04-29T00:00:00Z","timestamp":1461888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>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\u2013protein interaction networks annotated with synthetic and real gene ontology terms. Case studies have been done by querying protein complexes among different species and tissues.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>APPAGATO has been developed on top of CUDA-C\u2009++\u2009Toolkit 7.0 framework. The software is available online http:\/\/profs.sci.univr.it\/\u223cbombieri\/APPAGATO.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw223","type":"journal-article","created":{"date-parts":[[2016,4,30]],"date-time":"2016-04-30T01:35:22Z","timestamp":1461980122000},"page":"2159-2166","source":"Crossref","is-referenced-by-count":10,"title":["APPAGATO: an APproximate PArallel and stochastic GrAph querying TOol for biological networks"],"prefix":"10.1093","volume":"32","author":[{"given":"Vincenzo","family":"Bonnici","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Verona, Strada Le Grazie, Verona"}]},{"given":"Federico","family":"Busato","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Strada Le Grazie, Verona"}]},{"given":"Giovanni","family":"Micale","sequence":"additional","affiliation":[{"name":"Department of Math and Computer Science, University of Catania, Viale a. Doria, Catania"}]},{"given":"Nicola","family":"Bombieri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Strada Le Grazie, Verona"}]},{"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[{"name":"Department of Clinical and Experimental Medicine, University of Catania, via Palermo, Catania"}]},{"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Strada Le Grazie, Verona"},{"name":"Department of Clinical and Experimental Medicine, University of Catania, via Palermo, Catania"}]}],"member":"286","published-online":{"date-parts":[[2016,4,29]]},"reference":[{"key":"2023020112440548100_btw223-B1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1038\/nrg1272","article-title":"Network biology: understanding the cell\u2019s functional organization","volume":"5","author":"Barabasi","year":"2004","journal-title":"Nat. Rev. Genet"},{"key":"2023020112440548100_btw223-B2","first-page":"159","author":"Billeter","year":"2009"},{"key":"2023020112440548100_btw223-B3","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1109\/TCBB.2010.53","article-title":"Querying graphs in protein-protein interactions networks using feedback vertex set","volume":"7","author":"Blin","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"issue":"99","key":"2023020112440548100_btw223-B4","first-page":"1545","article-title":"On the variable ordering in subgraph isomorphism algorithms","volume":"PP","author":"Bonnici","year":"2016","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020112440548100_btw223-B5","doi-asserted-by":"crossref","first-page":"S13","DOI":"10.1186\/1471-2105-14-S7-S13","article-title":"A subgraph isomorphism algorithm and its application to biochemical data","volume":"14(Suppl. 7)","author":"Bonnici","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023020112440548100_btw223-B6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1089\/cmb.2009.0170","article-title":"Topology-free querying of protein interaction networks","volume":"17","author":"Bruckner","year":"2010","journal-title":"J. Comput. Biol"},{"key":"2023020112440548100_btw223-B7","doi-asserted-by":"crossref","first-page":"1826","DOI":"10.1109\/TPDS.2014.2330597","article-title":"BFS-4K: an efficient implementation of BFS for kepler GPU architectures","volume":"26","author":"Busato","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst"},{"key":"2023020112440548100_btw223-B8","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1101\/gr.125567.111","article-title":"Mutual exclusivity analysis identifies oncogenic network modules","volume":"22","author":"Ciriello","year":"2012","journal-title":"Genome Res"},{"key":"2023020112440548100_btw223-B9","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub) graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"2023020112440548100_btw223-B10","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"2023020112440548100_btw223-B11","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1038\/nmeth.3440","article-title":"Pathway and network analysis of cancer genomes","volume":"12","author":"Creixell","year":"2015","journal-title":"Nat. Methods"},{"key":"2023020112440548100_btw223-B12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1093\/bib\/bbq006","article-title":"Gpu computing for systems biology","volume":"11","author":"Dematt\u00e9","year":"2010","journal-title":"Brief. Bioinform"},{"key":"2023020112440548100_btw223-B13","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1089\/cmb.2007.0172","article-title":"Qnet: a tool for querying protein interaction networks","volume":"15","author":"Dost","year":"2008","journal-title":"J. Comput. Biol"},{"key":"2023020112440548100_btw223-B14","article-title":"Method inferring the functions of longevity genes with modular subnetwork biomarkers of Caenorhabditis elegans aging","volume-title":"Genom Biol","author":"Fortney","year":"2010"},{"key":"2023020112440548100_btw223-B15","doi-asserted-by":"crossref","first-page":"i149","DOI":"10.1093\/bioinformatics\/btr203","article-title":"RINQ: reference-based indexing for network queries","volume":"27","author":"Gulsoy","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B16","volume-title":"GPU Gems 3: Parallel Prefix Sum (Scan) with CUDA","author":"Harris","year":"2008"},{"key":"2023020112440548100_btw223-B17","doi-asserted-by":"crossref","first-page":"2507","DOI":"10.1109\/TKDE.2015.2391125","article-title":"Subgraph matching with set similarity in a large graph database","volume":"27","author":"Hong","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng"},{"key":"2023020112440548100_btw223-B18","doi-asserted-by":"crossref","first-page":"S233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","article-title":"Discovering regulatory and signalling circuits in molecular interaction networks","volume":"18(Suppl. 1)","author":"Ideker","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B19","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1111\/j.1541-0420.2010.01519.x","article-title":"Network-based auto-probit modeling for protein function prediction","volume":"67","author":"Jiang","year":"2011","journal-title":"Biometrics"},{"key":"2023020112440548100_btw223-B20","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"PNAS"},{"key":"2023020112440548100_btw223-B21","doi-asserted-by":"crossref","first-page":"W83","DOI":"10.1093\/nar\/gkh411","article-title":"PathBLAST: a tool for alignment of protein interaction networks","volume":"1","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020112440548100_btw223-B22","first-page":"181","author":"Khan","year":"2013"},{"key":"2023020112440548100_btw223-B23","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1126\/science.8211139","article-title":"Detecting subtle sequence signals: a gibbs sampling strategy for multiple alignment","volume":"262","author":"Lawrence","year":"1993","journal-title":"Science"},{"key":"2023020112440548100_btw223-B24","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1016\/j.cell.2006.03.032","article-title":"A protein\u2013protein interaction network for human inherited ataxias and disorders of purkinje cell degeneration","volume":"125","author":"Lim","year":"2006","journal-title":"Cell"},{"key":"2023020112440548100_btw223-B25","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1093\/bfgp\/els045","article-title":"Biological network analysis: insights into structure and functions","volume":"11","author":"Ma","year":"2012","journal-title":"Brief. Funct. Genomics"},{"key":"2023020112440548100_btw223-B26","doi-asserted-by":"crossref","first-page":"2182","DOI":"10.1093\/bioinformatics\/btv130","article-title":"L-GRAAL: Lagrangian graphlet-based network aligner","volume":"31","author":"Malod-Dognin","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B27","doi-asserted-by":"crossref","first-page":"e98750.","DOI":"10.1371\/journal.pone.0098750","article-title":"GASOLINE: a greedy and stochastic algorithm for optimal local multiple alignment of interaction networks","volume":"9","author":"Micale","year":"2014","journal-title":"PLoS ONE"},{"key":"2023020112440548100_btw223-B28","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1093\/bib\/bbt084","article-title":"Searching for repetitions in biological networks: methods, resources and tools","volume":"16","author":"Panni","year":"2015","journal-title":"Brief. Bioinform"},{"key":"2023020112440548100_btw223-B29","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/BigData.2014.7004278","volume-title":"2014 IEEE International Conference on Big Data, Big Data 2014","author":"Pienta","year":"2014"},{"key":"2023020112440548100_btw223-B30","doi-asserted-by":"crossref","first-page":"3401","DOI":"10.1093\/bioinformatics\/bti554","article-title":"Alignment of metabolic pathways","volume":"21","author":"Pinter","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B31","doi-asserted-by":"crossref","first-page":"D497","DOI":"10.1093\/nar\/gkp914","article-title":"CORUM: the comprehensive resource of mammalian protein complexes","volume":"38(Suppl. 1)","author":"Ruepp","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023020112440548100_btw223-B32","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1093\/bioinformatics\/bts341","article-title":"RESQUE: Network reduction using semi-Markov random walk scores for efficient querying of biological networks","volume":"28","author":"Sahraeian","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B33","doi-asserted-by":"crossref","first-page":"199.","DOI":"10.1186\/1471-2105-7-199","article-title":"QPath: a method for querying pathways in a protein-protein interaction network","volume":"10","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020112440548100_btw223-B34","doi-asserted-by":"crossref","first-page":"788","DOI":"10.14778\/2311906.2311907","article-title":"Efficient subgraph matching on billion node graphs","volume":"5","author":"Sun","year":"2012","journal-title":"Proc. VLDB Endow"},{"key":"2023020112440548100_btw223-B35","doi-asserted-by":"crossref","first-page":"D561","DOI":"10.1093\/nar\/gkq973","article-title":"The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored","volume":"39","author":"Szklarczyk","year":"2011","journal-title":"Nucleic Acids Res"},{"key":"2023020112440548100_btw223-B36","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1093\/bioinformatics\/btl571","article-title":"SAGA: a subgraph matching tool for biological graphs","volume":"15","author":"Tian","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B37","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.14778\/1454159.1454184","article-title":"Periscope\/gq: a graph querying toolkit","volume":"1","author":"Tian","year":"2008","journal-title":"Proc. VLDB Endow"},{"key":"2023020112440548100_btw223-B38","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1093\/bioinformatics\/btq644","article-title":"GPU-BLAST: using graphics processors to accelerate protein sequence alignment","volume":"27","author":"Vouzis","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020112440548100_btw223-B39","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1089\/cmb.2012.0272","article-title":"Function\u2013function correlated multi-label protein function prediction over interaction networks","volume":"20","author":"Wang","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023020112440548100_btw223-B40","doi-asserted-by":"crossref","first-page":"200","DOI":"10.5808\/GI.2013.11.4.200","article-title":"Review of biological network data and its applications","volume":"11","author":"Yu","year":"2013","journal-title":"Genomics Inform"},{"key":"2023020112440548100_btw223-B41","first-page":"963","volume-title":"Data IEEE 24th International Conference on Engineering, 2008, ICDE 2008","author":"Yuanyuan","year":"2008"},{"key":"2023020112440548100_btw223-B42","first-page":"192","author":"Zhang","year":"2009"},{"key":"2023020112440548100_btw223-B43","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1093\/bioinformatics\/btu047","article-title":"G-BLASTN: accelerating nucleotide alignment by graphics processors","volume":"30","author":"Zhao","year":"2014","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/14\/2159\/49019480\/bioinformatics_32_14_2159.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/14\/2159\/49019480\/bioinformatics_32_14_2159.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:48:33Z","timestamp":1675291713000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/14\/2159\/1743635"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2016,4,29]]},"references-count":43,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2016,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw223","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,7,15]]},"published":{"date-parts":[[2016,4,29]]}}}