{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:45:11Z","timestamp":1740185111880,"version":"3.37.3"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2017,1,31]],"date-time":"2017-01-31T00:00:00Z","timestamp":1485820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/100007567","name":"City University of Hong Kong","doi-asserted-by":"publisher","award":["72004444"],"award-info":[{"award-number":["72004444"]}],"id":[{"id":"10.13039\/100007567","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Grant Council","award":["9048072","21200816"],"award-info":[{"award-number":["9048072","21200816"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The exponential growth of biological network database has increasingly rendered the global network similarity search (NSS) computationally intensive. Given a query network and a network database, it aims to find out the top similar networks in the database against the query network based on a topological similarity measure of interest. With the advent of big network data, the existing search methods may become unsuitable since some of them could render queries unsuccessful by returning empty answers or arbitrary query restrictions. Therefore, the design of NSS algorithm remains challenging under the dilemma between accuracy and efficiency.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We propose a global NSS method based on regression, denotated as NSSRF, which boosts the search speed without any significant sacrifice in practical performance. As motivated from the nature, subgraph signatures are heavily involved. Two phases are proposed in NSSRF: offline model building phase and similarity query phase. In the offline model building phase, the subgraph signatures and cosine similarity scores are used for efficient random forest regression (RFR) model training. In the similarity query phase, the trained regression model is queried to return similar networks. We have extensively validated NSSRF on biological pathways and molecular structures; NSSRF demonstrates competitive performance over the state-of-the-arts. Remarkably, NSSRF works especially well for large networks, which indicates that the proposed approach can be promising in the era of big data. Case studies have proven the efficiencies and uniqueness of NSSRF which could be missed by the existing state-of-the-arts.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and Implementation<\/jats:title>\n                  <jats:p>The source code of two versions of NSSRF are freely available for downloading at https:\/\/github.com\/zhangjiaobxy\/nssrfBinary and https:\/\/github.com\/zhangjiaobxy\/nssrfPackage.<\/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\/btx051","type":"journal-article","created":{"date-parts":[[2017,1,30]],"date-time":"2017-01-30T13:28:22Z","timestamp":1485782902000},"page":"1696-1702","source":"Crossref","is-referenced-by-count":6,"title":["NSSRF: global network similarity search with subgraph signatures and its applications"],"prefix":"10.1093","volume":"33","author":[{"given":"Jiao","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Kwong","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuheng","family":"Jia","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ka-Chun","family":"Wong","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2017,1,31]]},"reference":[{"key":"2023020205302292300_btx051-B1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet"},{"year":"1998","author":"Bank","key":"2023020205302292300_btx051-B2"},{"first-page":"195","year":"2010","author":"Bonnici","key":"2023020205302292300_btx051-B3"},{"key":"2023020205302292300_btx051-B4","doi-asserted-by":"crossref","first-page":"2159","DOI":"10.1093\/bioinformatics\/btw223","article-title":"APPAGATO: an APproximate PArallel and stochastic GrAph querying TOol for biological networks","volume":"32","author":"Bonnici","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Mach. Learn"},{"key":"2023020205302292300_btx051-B6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0167-8655(97)00179-7","article-title":"A graph distance metric based on the maximal common subgraph","volume":"19","author":"Bunke","year":"1998","journal-title":"Patt. Recogn. Lett"},{"key":"2023020205302292300_btx051-B7","doi-asserted-by":"crossref","first-page":"D470","DOI":"10.1093\/nar\/gku1204","article-title":"The biogrid interaction database: 2015 update","volume":"43","author":"Chatr-Aryamontri","year":"2015","journal-title":"Nucleic Acids Res"},{"first-page":"151","year":"1971","author":"Cook","key":"2023020205302292300_btx051-B8"},{"key":"2023020205302292300_btx051-B9","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1126\/science.1069883","article-title":"A genomic regulatory network for development","volume":"295","author":"Davidson","year":"2002","journal-title":"Science"},{"key":"2023020205302292300_btx051-B10","article-title":"Survey on the graph alignment problem and a benchmark of suitable algorithms. Bachelor's Thesis","author":"D\u00f6pmann","year":"2013","journal-title":"Institut F\u00fcr Informatik"},{"key":"2023020205302292300_btx051-B11","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/s13637-015-0022-9","article-title":"The post-genomic era of biological network alignment","volume":"2015","author":"Faisal","year":"2015","journal-title":"EURASIP J. Bioinf. Syst. Biol"},{"key":"2023020205302292300_btx051-B12","first-page":"3133","article-title":"Do we need hundreds of classifiers to solve real world classification problems","volume":"15","author":"Fern\u00e1ndez-Delgado","year":"2014","journal-title":"J. Mach. Learn. Res"},{"key":"2023020205302292300_btx051-B13","doi-asserted-by":"crossref","first-page":"i149","DOI":"10.1093\/bioinformatics\/btr203","article-title":"Rinq: Reference-based indexing for network queries","volume":"27","author":"G\u00fclsoy","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B14","doi-asserted-by":"crossref","first-page":"i438","DOI":"10.1093\/bioinformatics\/btu450","article-title":"Hubalign: an accurate and efficient method for global alignment of protein\u2013protein interaction networks","volume":"30","author":"Hashemifar","year":"2014","journal-title":"Bioinformatics"},{"first-page":"38","year":"2006","author":"He","key":"2023020205302292300_btx051-B15"},{"key":"2023020205302292300_btx051-B16","first-page":"547","article-title":"A comparative study of the floral distribution in alps and jura","volume":"37","author":"Jaccard","year":"1901","journal-title":"Bull. Walden Soc. Nat. Sci"},{"first-page":"566","year":"2007","author":"Jiang","key":"2023020205302292300_btx051-B17"},{"key":"2023020205302292300_btx051-B18","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1093\/bioinformatics\/btm630","article-title":"Networkblast: comparative analysis of protein networks","volume":"24","author":"Kalaev","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B19","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1093\/nar\/28.1.27","article-title":"Kegg: kyoto encyclopedia of genes and genomes","volume":"28","author":"Kanehisa","year":"2000","journal-title":"Nucleic Acids Res"},{"key":"2023020205302292300_btx051-B20","doi-asserted-by":"crossref","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","article-title":"Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs","volume":"20","author":"Kashtan","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B21","doi-asserted-by":"crossref","first-page":", D1301","DOI":"10.1093\/nar\/gkr1074","article-title":"Wikipathways: building research communities on biological pathways","volume":"40","author":"Kelder","year":"2012","journal-title":"Nucleic Acids Res"},{"first-page":"181","year":"2013","author":"Khan","key":"2023020205302292300_btx051-B22"},{"key":"2023020205302292300_btx051-B23","first-page":"gkw1039.","article-title":"The Human Phenotype Ontology in 2017","author":"K\u00f6hler","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020205302292300_btx051-B24","first-page":"15","article-title":"Mixed-data classificatory programs i \u2013 agglomerative systems","volume":"1","author":"Lance","year":"1967","journal-title":"Aust. Comput. J"},{"key":"2023020205302292300_btx051-B25","doi-asserted-by":"crossref","first-page":"11980","DOI":"10.1073\/pnas.2133841100","article-title":"Structure and function of the feed-forward loop network motif","volume":"100","author":"Mangan","year":"2003","journal-title":"Proc. Natl. Acad. Sci"},{"key":"2023020205302292300_btx051-B26","doi-asserted-by":"crossref","first-page":"3155","DOI":"10.1093\/bioinformatics\/btw348","article-title":"Local versus global biological network alignment","volume":"32","author":"Meng","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B27","first-page":"121.","article-title":"Optimal network alignment with graphlet degree vectors","volume":"9","author":"Milenkovic","year":"2010","journal-title":"Cancer Inf"},{"key":"2023020205302292300_btx051-B28","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2023020205302292300_btx051-B29","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. Bioinf. Comput. Biol"},{"key":"2023020205302292300_btx051-B30","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1093\/bioinformatics\/btt202","article-title":"Netal: a new graph-based method for global alignment of protein\u2013protein interaction networks","volume":"29","author":"Neyshabur","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020205302292300_btx051-B31","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. Bioinf"},{"first-page":"585","year":"2014","author":"Pienta","key":"2023020205302292300_btx051-B32"},{"key":"2023020205302292300_btx051-B33","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1093\/comjnl\/45.6.631","article-title":"Rascal: Calculation of graph similarity using maximum common edge subgraphs","volume":"45","author":"Raymond","year":"2002","journal-title":"Comput. J"},{"key":"2023020205302292300_btx051-B34","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechnol"},{"first-page":"1","year":"2015","author":"Soylev","key":"2023020205302292300_btx051-B35"},{"key":"2023020205302292300_btx051-B36","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1021\/ci9800211","article-title":"Chemical similarity searching","volume":"38","author":"Willett","year":"1998","journal-title":"J. Chem. Inf. Comput. Sci"},{"key":"2023020205302292300_btx051-B37","first-page":"msv031.","article-title":"Genomic and network patterns of schizophrenia genetic variation in human evolutionary accelerated regions","author":"Xu","year":"2015","journal-title":"Mol. Biol.Evol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/11\/1696\/49039832\/bioinformatics_33_11_1696.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/11\/1696\/49039832\/bioinformatics_33_11_1696.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T05:32:08Z","timestamp":1675315928000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/11\/1696\/2964730"}},"subtitle":[],"editor":[{"given":"Jonathan","family":"Wren","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2017,1,31]]},"references-count":37,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx051","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2017,6,1]]},"published":{"date-parts":[[2017,1,31]]}}}