{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T05:54:09Z","timestamp":1675317249962},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1937,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.<\/jats:p>\n               <jats:p>Contact: \u00a0ggulsoy@cise.ufl.edu; tamer@cise.ufl.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr203","type":"journal-article","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T23:32:32Z","timestamp":1308353552000},"page":"i149-i158","source":"Crossref","is-referenced-by-count":9,"title":["RINQ: Reference-based Indexing for Network Queries"],"prefix":"10.1093","volume":"27","author":[{"given":"G\u00fcnhan","family":"G\u00fclsoy","sequence":"first","affiliation":[{"name":"Computer and Information Sciences and Engineering Department, University of Florida, Gainesville, FL 32611, USA"}]},{"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[{"name":"Computer and Information Sciences and Engineering Department, University of Florida, Gainesville, FL 32611, USA"}]}],"member":"286","published-online":{"date-parts":[[2011,6,14]]},"reference":[{"key":"2023012512023414100_B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023012512023414100_B2","first-page":"15","article-title":"SubMAP: aligning metabolic pathways with subnetwork mappings","volume-title":"International Conference on Research in Computational Molecular Biology, Lecture Notes in Computer Science","author":"Ay","year":"2010"},{"key":"2023012512023414100_B3","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1142\/S0219720009004163","article-title":"A fast and accurate algorithm for comparative analysis of metabolic pathways","volume":"7","author":"Ay","year":"2009","journal-title":"J. Bioinformatics Comput. Biol."},{"key":"2023012512023414100_B4","doi-asserted-by":"crossref","first-page":"R138","DOI":"10.1186\/gb-2008-9-9-r138","article-title":"Netgrep: fast network schema searches in interactomes","volume":"9","author":"Banks","year":"2008","journal-title":"Genome Biol."},{"issue":"Suppl. 2","key":"2023012512023414100_B5","doi-asserted-by":"crossref","first-page":"W106","DOI":"10.1093\/nar\/gkp474","article-title":"Torque: topology-free querying of protein interaction networks","volume":"37","author":"Bruckner","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012512023414100_B6","first-page":"45","article-title":"Reconstruction of phylogenetic relationships from metabolic pathways based on the enzyme hierarchy and the gene ontology","volume":"16","author":"Clemente","year":"2005","journal-title":"Genome Inform."},{"key":"2023012512023414100_B7","first-page":"46","article-title":"Finding conserved and non-conserved reactions using a metabolic pathway alignment algorithm","volume":"17","author":"Clemente","year":"2006","journal-title":"Genome Inform."},{"key":"2023012512023414100_B8","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":"2023012512023414100_B9","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1093\/bioinformatics\/btm032","article-title":"NetMatch: a Cytoscape plugin for searching biological networks","volume":"23","author":"Ferro","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012512023414100_B10","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1016\/j.tim.2005.09.001","article-title":"Reconstructing the metabolic network of a bacterium from its genome","volume":"13","author":"Francke","year":"2005","journal-title":"Trends Microbiol."},{"key":"2023012512023414100_B11","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1126\/science.1090289","article-title":"A protein interaction map of drosophila melanogaster","volume":"302","author":"Giot","year":"2003","journal-title":"Science"},{"key":"2023012512023414100_B12","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1109\/ICPR.2002.1048250","article-title":"GraphGrep: a fast and universal method for querying graphs","volume":"2","author":"Giugno","year":"2002","journal-title":"Proceedings of 16th International Pattern Recognition Conference"},{"key":"2023012512023414100_B13","first-page":"38","article-title":"Closure-Tree: an index structure for graph queries","volume":"0","author":"He","year":"2006","journal-title":"Int. Conf. Data Eng."},{"key":"2023012512023414100_B14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1038\/nrc1609","article-title":"Erbb receptors and cancer: the complexity of targeted inhibitors","volume":"5","author":"Hynes","year":"2005","journal-title":"Nat. Rev. Cancer"},{"key":"2023012512023414100_B15","doi-asserted-by":"crossref","first-page":"W83","DOI":"10.1093\/nar\/gkh411","article-title":"PathBLAST: a tool for alignment of protein interaction networks","volume":"32","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012512023414100_B16","doi-asserted-by":"crossref","first-page":"4936","DOI":"10.1073\/pnas.0408031102","article-title":"Gene regulatory networks for development","volume":"102","author":"Levine","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512023414100_B17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"IsoRankN: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512023414100_B18","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1142\/S021972001000477X","article-title":"SIGMA: a set-cover-based inexact graph matching algorithm","volume":"8","author":"Mongiovi","year":"2010","journal-title":"J. Bioinformatics Comput. Biol."},{"key":"2023012512023414100_B19","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1093\/nar\/27.1.29","article-title":"KEGG: Kyoto Encyclopedia of Genes and Genomes","volume":"27","author":"Ogata","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012512023414100_B20","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":"2023012512023414100_B21","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":"7","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012512023414100_B22","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-71681-5_2","article-title":"Pairwise global alignment of protein interaction networks by matching neighborhood topology","volume-title":"Research in Computational Molecular Biology, Lecture Notes in Computer Science","author":"Singh","year":"2007"},{"key":"2023012512023414100_B23","first-page":"88","article-title":"An iterative algorithm for metabolic network-based drug target identification","volume":"12","author":"Sridhar","year":"2007","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012512023414100_B24","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1093\/bioinformatics\/btl571","article-title":"SAGA: a subgraph matching tool for biological graphs","volume":"23","author":"Tian","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012512023414100_B25","first-page":"335","article-title":"Graph indexing: a frequent structure-based approach","volume-title":"SIGMOD","author":"Yan","year":"2004"},{"key":"2023012512023414100_B26","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1038\/35052073","article-title":"Untangling the erbb signalling network","volume":"2","author":"Yarden","year":"2001","journal-title":"Nat. Rev. Mol. Cell Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i149\/48876782\/bioinformatics_27_13_i149.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i149\/48876782\/bioinformatics_27_13_i149.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T14:22:09Z","timestamp":1674656529000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/13\/i149\/177189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,14]]},"references-count":26,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2011,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr203","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,7,1]]},"published":{"date-parts":[[2011,6,14]]}}}