{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T18:33:23Z","timestamp":1718130803110},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,10,9]],"date-time":"2015-10-09T00:00:00Z","timestamp":1444348800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s12859-015-0756-0","type":"journal-article","created":{"date-parts":[[2015,10,9]],"date-time":"2015-10-09T12:06:00Z","timestamp":1444392360000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Indexing a protein-protein interaction network expedites network alignment"],"prefix":"10.1186","volume":"16","author":[{"given":"Md Mahmudul","family":"Hasan","sequence":"first","affiliation":[]},{"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,10,9]]},"reference":[{"issue":"2","key":"756_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1038\/nrg1272","volume":"5","author":"AL Barab\u00e1si","year":"2004","unstructured":"Barab\u00e1si AL, Oltvai ZN. Network biology: understanding the cell\u2019s functional organization. Nat Rev Genet. 2004; 5(2):101\u201313.","journal-title":"Nat Rev Genet"},{"issue":"2","key":"756_CR2","first-page":"46","volume":"17","author":"JC Clemente","year":"2006","unstructured":"Clemente JC, Satou K, Valiente G. Finding conserved and non-conserved reactions using a metabolic pathway alignment algorithm. Genome Inform. 2006; 17(2):46\u201356.","journal-title":"Genome Inform"},{"issue":"11","key":"756_CR3","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1016\/j.tim.2005.09.001","volume":"13","author":"C Francke","year":"2005","unstructured":"Francke C, Siezen RJ, Teusink B. Reconstructing the metabolic network of a bacterium from its genome. Trends Microbiol. 2005; 13(11):550\u20138.","journal-title":"Trends Microbiol"},{"issue":"12","key":"756_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1093\/bioinformatics\/btp203","volume":"25","author":"CS Liao","year":"2009","unstructured":"Liao CS, Lu K, Baym M, Singh R, Berger B. IsoRankN: Spectral methods for global alignment of multiple protein networks. Bioinformatics. 2009; 25(12):253\u20138.","journal-title":"Bioinformatics"},{"issue":"50","key":"756_CR5","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","volume":"7","author":"O Kuchaiev","year":"2010","unstructured":"Kuchaiev O, Milenkovi\u0107 T, Memi\u0161evi\u0107 V, Hayes W, Pr\u017eulj N. Topological network alignment uncovers biological function and phylogeny. J R Soc Interface. 2010; 7(50):1341\u20131354.","journal-title":"J R Soc Interface"},{"issue":"7","key":"756_CR6","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1089\/cmb.2007.0172","volume":"15","author":"B Dost","year":"2008","unstructured":"Dost B, Shlomi T, Gupta N, Ruppin E, Bafna V, Sharan R. QNet: A tool for querying protein interaction networks. J Comput Biol. 2008; 15(7):913\u201325.","journal-title":"J Comput Biol"},{"issue":"Web-Server-Issu","key":"756_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/nar\/gkh411","volume":"32","author":"BP Kelley","year":"2004","unstructured":"Kelley BP, Yuan B, Lewitter F, Sharan R, Stockwell BR, Ideker T. PathBLAST: a tool for alignment of protein interaction networks. Nucleic Acids Res. 2004; 32(Web-Server-Issue):83\u20138.","journal-title":"Nucleic Acids Res"},{"issue":"20","key":"756_CR8","doi-asserted-by":"publisher","first-page":"11394","DOI":"10.1073\/pnas.1534710100","volume":"100","author":"BP Kelley","year":"2003","unstructured":"Kelley BP, Sharan R, Karp RM, Sittler T, Root DE, Stockwell BR, et al. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc Natl Acad Sci USA. 2003; 100(20):11394\u20139.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"5","key":"756_CR9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/2160718.2160738","volume":"55","author":"N Atias","year":"2012","unstructured":"Atias N, Sharan R. Comparative analysis of protein networks: hard problems, practical solutions. Commun ACM. 2012; 55(5):88\u201397.","journal-title":"Commun ACM"},{"key":"756_CR10","volume-title":"ACM BCB","author":"H Md Mahmudul","year":"2013","unstructured":"Md Mahmudul H, Tamer K. Color distribution can accelerate network alignment. In: ACM BCB. New York, USA: ACM: 2013. p. 52\u201361."},{"key":"756_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139164849","volume-title":"Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica","author":"S Pemmaraju","year":"2003","unstructured":"Pemmaraju S, Skiena S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. England: Cambridge University Press; 2003."},{"key":"756_CR12","volume-title":"STOC","author":"SA Cook","year":"1971","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: STOC. New York, USA: ACM: 1971. p. 151\u20138."},{"key":"756_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1089\/cmb.2010.0280","volume":"18","author":"F Ay","year":"2011","unstructured":"Ay F, Kellis M, Kahveci T. SubMAP: Aligning metabolic pathways with subnetwork mapping. J Comput Biol. 2011; 18:219\u201335.","journal-title":"J Comput Biol"},{"key":"756_CR14","volume-title":"Software pioneers","year":"2002","unstructured":"Bayer R. In: (Broy M, Denert E, editors.)Software pioneers. New York, NY, USA: Springer-Verlag New York, Inc.; 2002, pp. 232\u2013244. B-trees and Databases, Past and Future."},{"key":"756_CR15","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266","volume-title":"R-trees: a Dynamic Index Structure for Spatial Searching","author":"A Guttman","year":"1984","unstructured":"Guttman A, Vol. 14. R-trees: a Dynamic Index Structure for Spatial Searching. USA: ACM; 1984."},{"issue":"5594","key":"756_CR16","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002; 298(5594):824\u20137.","journal-title":"Science"},{"key":"756_CR17","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/bioinformatics\/bti1049","volume":"21","author":"H Hu","year":"2005","unstructured":"Hu H, Yan X, Huang Y, Han J, Zhou XJ. Mining coherent dense subgraphs across massive biological networks for discovery. Bioinformatics. 2005; 21:213\u201321.","journal-title":"Bioinformatics"},{"issue":"S-4","key":"756_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1752-0509-7-S4-S3","volume":"7","author":"MM Hasan","year":"2013","unstructured":"Hasan MM, Kavurucu Y, Kahveci T. A scalable method for discovering significant subnetworks. BMC Syst Biol. 2013; 7(S-4):3.","journal-title":"BMC Syst Biol"},{"key":"756_CR19","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","volume":"13","author":"M Koyut\u00fcrk","year":"2006","unstructured":"Koyut\u00fcrk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A. Pairwise alignment of protein interaction networks. J Comput Biol. 2006; 13:182\u201399.","journal-title":"J Comput Biol"},{"issue":"3","key":"756_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1089\/cmb.2009.0170","volume":"17","author":"S Bruckner","year":"2010","unstructured":"Bruckner S, H\u00fcffner F, Karp RM, Shamir R, Sharan R. Topology-free querying of protein interaction networks. J Comput Biol : J Comput Mol Cell Biol. 2010; 17(3):237\u201352.","journal-title":"J Comput Biol : J Comput Mol Cell Biol"},{"key":"756_CR21","volume-title":"Proceedings of the 2008 IEEE 24th International Conference on Data Engineering","author":"Y Tian","year":"2008","unstructured":"Tian Y, Patel JM. TALE: A Tool for Approximate Large Graph Matching. In: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society: 2008. p. 963\u201372."},{"issue":"4","key":"756_CR22","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1109\/TCBB.2011.29","volume":"8","author":"N Ferraro","year":"2011","unstructured":"Ferraro N, Palopoli L, Panni S, Rombo SE. Asymmetric Comparison, Querying of Biological Networks. IEEE\/ACM Trans Comput Biol Bioinform. 2011; 8(4):876\u201389.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"7","key":"756_CR23","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1093\/bioinformatics\/btm032","volume":"23","author":"A Ferro","year":"2007","unstructured":"Ferro A, Giugno R, Pigola G, Pulvirenti A, Skripin D, Bader GD, et al. NetMatch: a Cytoscape plugin for searching biological networks. Bioinformatics. 2007; 23(7):910\u20132.","journal-title":"Bioinformatics"},{"issue":"4","key":"756_CR24","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon N, Yuster R, Zwick U. Color-coding. J ACM. 1995; 42(4):844\u201356.","journal-title":"J ACM"},{"key":"756_CR25","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1186\/1471-2105-7-199","volume":"7","author":"T Shlomi","year":"2006","unstructured":"Shlomi T, Segal D, Rupin E, Sharan R. QPath: A method for querying pathways in a protein-protein intraction network. BMC Bioinformatics. 2006; 7:199.","journal-title":"BMC Bioinformatics"},{"issue":"35","key":"756_CR26","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","volume":"105","author":"R Singh","year":"2008","unstructured":"Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc Natl Acad Sci. 2008; 105(35):12763\u20138.","journal-title":"Proc Natl Acad Sci"},{"issue":"6","key":"756_CR27","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1093\/bioinformatics\/btq091","volume":"26","author":"N Pr\u017eulj","year":"2010","unstructured":"Pr\u017eulj N. Biological network comparison using graphlet degree distribution. Bioinformatics. 2010; 26(6):853\u20134.","journal-title":"Bioinformatics"},{"key":"756_CR28","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4137\/CIN.S4744","volume":"9","author":"T Milenkovi\u0107","year":"2010","unstructured":"Milenkovi\u0107 T, Ng WL, Hayes W, Przulj N. Optimal network alignment with graphlet degree vectors. Cancer Inform. 2010; 9:121\u201337.","journal-title":"Cancer Inform"},{"issue":"2","key":"756_CR29","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1093\/bioinformatics\/btl571","volume":"23","author":"Y Tian","year":"2007","unstructured":"Tian Y, McEachin RC, Santos C, States DJ, Patel JM. SAGA: a subgraph matching tool for biological graphs. Bioinformatics. 2007; 23(2):232\u20139.","journal-title":"Bioinformatics"},{"issue":"2","key":"756_CR30","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1142\/S021972001000477X","volume":"8","author":"M Mongiov\u00ec","year":"2010","unstructured":"Mongiov\u00ec M, Di Natale R, Giugno R, Pulvirenti A, Ferro A, Sharan R. SIGMA: a set-cover-based inexact graph matching algorithm. J Bioinforma Comput Biol. 2010; 8(2):199\u2013218.","journal-title":"J Bioinforma Comput Biol"},{"key":"756_CR31","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/1471-2105-11-96","volume":"11","author":"R Di Natale","year":"2010","unstructured":"Di Natale R, Ferro A, Giugno R, Mongiov\u00ec M, Pulvirenti A, Shasha D. SING: subgraph search in non-homogeneous graphs. BMC Bioinformatics. 2010; 11:96.","journal-title":"BMC Bioinformatics"},{"key":"756_CR32","volume-title":"Proceedings of the 22Nd International Conference on Data Engineering, ICDE \u201906","author":"He Huahai","year":"2006","unstructured":"Huahai He, Ambuj KS. Closure-Tree: An index structure for graph queries. In: Proceedings of the 22Nd International Conference on Data Engineering, ICDE \u201906. Washington, DC, USA: IEEE Computer Society: 2006. p. 38."},{"issue":"13","key":"756_CR33","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1093\/bioinformatics\/btr203","volume":"27","author":"G G\u00fclsoy","year":"2011","unstructured":"G\u00fclsoy G, Kahveci T. RINQ: Reference-based indexing for network queries. Bioinformatics. 2011; 27(13):149\u201358.","journal-title":"Bioinformatics"},{"issue":"Suppl 3","key":"756_CR34","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/1471-2105-13-S3-S10","volume":"13","author":"BS Seah","year":"2012","unstructured":"Seah BS, Bhowmick SS, Jr Dewey CF, Yu H. FUSE: a profit maximization approach for functional summarization of biological networks. BMC Bioinformatics. 2012; 13(Suppl 3):10.","journal-title":"BMC Bioinformatics"},{"issue":"18","key":"756_CR35","doi-asserted-by":"publisher","first-page":"2619","DOI":"10.1093\/bioinformatics\/btu358","volume":"30","author":"BS Seah","year":"2014","unstructured":"Seah BS, Bhowmick SS1, Jr Dewey CF. DualAligner: a dual alignment-based strategy to align protein interaction networks. Bioinformatics. 2014; 30(18):2619\u201326.","journal-title":"Bioinformatics"},{"key":"756_CR36","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV. Approximation Algorithms. New York: Springer; 2001."},{"issue":"D1","key":"756_CR37","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1093\/nar\/gkr930","volume":"40","author":"L Licata","year":"2012","unstructured":"Licata L, Briganti L, Peluso D, Perfetto L, Iannuccelli M, Galeota E, et al. MINT, the molecular interaction database: 2012 update. Nucleic Acids Res. 2012; 40(D1):857\u201361.","journal-title":"Nucleic Acids Res"},{"key":"756_CR38","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1093\/nar\/28.1.289","volume":"28","author":"I Xenarios","year":"2000","unstructured":"Xenarios I, Rice DW, Salwinski L, Baron MK, Marcotte EM, Eisenberg D. DIP: The database of interacting proteins. Nucleic Acid Res. 2000; 28:289\u201391.","journal-title":"Nucleic Acid Res"},{"key":"756_CR39","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/gb-2004-5-12-r96","volume":"5","author":"CA Stanyon","year":"2004","unstructured":"Stanyon CA, Liu G, Mangiola BA, Patel N, Giot L, Kuang B, et al. A Drosophila protein-interaction map centered on cell-cycle regulators. Genome Biol. 2004; 5:96.","journal-title":"Genome Biol"},{"issue":"1","key":"756_CR40","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1093\/nar\/28.1.27","volume":"28","author":"M Kanehisa","year":"2000","unstructured":"Kanehisa M, Goto S. KEGG: Kyoto encyclopedia of genes and genomes. Nucleic Acids Res. 2000; 28(1):27\u201330.","journal-title":"Nucleic Acids Res"},{"issue":"suppl 1","key":"756_CR41","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1093\/nar\/gkh131","volume":"32","author":"R Apweiler","year":"2004","unstructured":"Apweiler R, Bairoch A, Wu CH, Barker WC, Boeckmann B, Ferro S, et al. UniProt: the universal protein knowledgebase. Nucleic Acids Res. 2004; 32(suppl 1):115\u20139.","journal-title":"Nucleic Acids Res"},{"key":"756_CR42","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW. The Hungarian method for the assignment problem. Nav Res Logist. 1955; 2:83\u201397.","journal-title":"Nav Res Logist"},{"issue":"1","key":"756_CR43","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1038\/nprot.2008.211","volume":"4","author":"W Huang Da","year":"2008","unstructured":"Huang Da W, Sherman BT, Lempicki RA. Systematic and integrative analysis of large gene lists using DAVID bioinformatics resources. Nat Protoc. 2008; 4(1):44\u201357.","journal-title":"Nat Protoc"},{"issue":"1","key":"756_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1093\/nar\/gkn923","volume":"37","author":"W Huang Da","year":"2009","unstructured":"Huang Da W, Sherman BT, Lempicki RA. Bioinformatics enrichment tools: paths toward the comprehensive functional analysis of large gene lists. Nucleic Acids Res. 2009; 37(1):1\u201313.","journal-title":"Nucleic Acids Res"},{"issue":"Database issue","key":"756_CR45","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/nar\/gku1243","volume":"43","author":"A Mitchell","year":"2015","unstructured":"Mitchell A, Chang HY, Daugherty L, Fraser M, Hunter S, Lopez R, et al. The InterPro protein families database: the classification resource after 15 years. Nucleic Acids Res. 2015; 43(Database issue):213\u201321.","journal-title":"Nucleic Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0756-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-015-0756-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0756-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T12:39:15Z","timestamp":1478867955000},"score":1,"resource":{"primary":{"URL":"http:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-015-0756-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,9]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["756"],"URL":"https:\/\/doi.org\/10.1186\/s12859-015-0756-0","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,9]]},"article-number":"326"}}