{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:12:26Z","timestamp":1717200746381},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"S5","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2006,12,18]],"date-time":"2006-12-18T00:00:00Z","timestamp":1166400000000},"content-version":"vor","delay-in-days":17,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>In recent times, there has been an exponential rise in the number of protein structures in databases e.g. PDB. So, design of fast algorithms capable of querying such databases is becoming an increasingly important research issue. This paper reports an algorithm, motivated from spectral graph matching techniques, for retrieving protein structures similar to a query structure from a large protein structure database. Each protein structure is specified by the 3D coordinates of residues of the protein. The algorithm is based on a novel characterization of the residues, called projections, leading to a similarity measure between the residues of the two proteins. This measure is exploited to efficiently compute the optimal equivalences.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Experimental results show that, the current algorithm outperforms the state of the art on benchmark datasets in terms of speed without losing accuracy. Search results on SCOP 95% nonredundant database, for fold similarity with 5 proteins from different SCOP classes show that the current method performs competitively with the standard algorithm CE. The algorithm is also capable of detecting non-topological similarities between two proteins which is not possible with most of the state of the art tools like Dali.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-7-s5-s5","type":"journal-article","created":{"date-parts":[[2006,12,19]],"date-time":"2006-12-19T07:17:42Z","timestamp":1166512662000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Projections for fast protein structure retrieval"],"prefix":"10.1186","volume":"7","author":[{"given":"Sourangshu","family":"Bhattacharya","sequence":"first","affiliation":[]},{"given":"Chiranjib","family":"Bhattacharyya","sequence":"additional","affiliation":[]},{"given":"Nagasuma R","family":"Chandra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,12,18]]},"reference":[{"key":"1355_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1093\/nar\/28.1.235","volume":"28","author":"HM Berman","year":"2000","unstructured":"Berman HM, Westbrook J, Feng Z, Gilliland G, Bhat TN, Weissig H, Shindyalov IN, Bourne PE: The Protein Data Bank. Nucleic Acids Research 2000, 28: 235\u2013242.","journal-title":"Nucleic Acids Research"},{"key":"1355_CR2","first-page":"512","volume-title":"FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"D Goldman","year":"1999","unstructured":"Goldman D, Papadimitriou CH, Istrail S: Algorithmic Aspects of Protein Structure Similarity. In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Washington, DC, USA: IEEE Computer Society; 1999:512."},{"key":"1355_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","volume":"233","author":"L Holm","year":"1993","unstructured":"Holm L, Sander C: Protein Structure Comparison by Alignment of Distance Matrices. Journal of Molecular Biology 1993, 233: 123\u2013138.","journal-title":"Journal of Molecular Biology"},{"issue":"5275","key":"1355_CR4","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1126\/science.273.5275.595","volume":"273","author":"L Holm","year":"1996","unstructured":"Holm L, Sander C: Mapping the Protein Universe. Science 1996, 273(5275):595\u2013602.","journal-title":"Science"},{"issue":"3","key":"1355_CR5","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1093\/protein\/6.3.279","volume":"6","author":"O Bachar","year":"1993","unstructured":"Bachar O, Fischer D, Nussinov R, Wolfson H: A Computer Vision Based Technique for 3-D Sequence Independent Structural Comparison of Proteins. Protein Engineering 1993, 6(3):279\u2013288.","journal-title":"Protein Engineering"},{"key":"1355_CR6","first-page":"284","volume":"5","author":"AP Singh","year":"1997","unstructured":"Singh AP, Brutlag DL: Hierarchical protein structure superposition using both secondary structure and atomic representations. Proceedings of International Conference on Intelligent Systems in Molecular Biology 1997, 5: 284\u2013293.","journal-title":"Proceedings of International Conference on Intelligent Systems in Molecular Biology"},{"key":"1355_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-2836(89)90084-3","volume":"208","author":"WR Taylor","year":"1989","unstructured":"Taylor WR, Orengo CA: Protein Structure Alignment. Journal of Molecular Biology 1989, 208: 1\u201322.","journal-title":"Journal of Molecular Biology"},{"issue":"9","key":"1355_CR8","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1093\/protein\/11.9.739","volume":"11","author":"PE Bourne","year":"1998","unstructured":"Bourne PE, Shindyalov IN: Protein structure alignment by incremental combinatorial extension of optimal path. Protein Engineering 1998, 11(9):739\u2013747.","journal-title":"Protein Engineering"},{"key":"1355_CR9","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/S0959-440X(97)80061-9","volume":"7","author":"Y Lindqvist","year":"1997","unstructured":"Lindqvist Y, Schneider G: Circular permutations of natural protein sequences: structural evidence. Current Opinion in Structural Biology 1997, 7: 422\u2013427.","journal-title":"Current Opinion in Structural Biology"},{"issue":"8","key":"1355_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1093\/protein\/14.8.533","volume":"14","author":"S Uliel","year":"2001","unstructured":"Uliel S, Fliess A, Unger R: Naturally occuring circular permutations in proteins. Protein Engineering 2001, 14(8):533\u2013542.","journal-title":"Protein Engineering"},{"key":"1355_CR11","doi-asserted-by":"publisher","first-page":"1881","DOI":"10.1110\/ps.05801","volume":"10","author":"J Jung","year":"2001","unstructured":"Jung J, Lee B: Circularly permuted proteins in the protein structure database. Protein Science 2001, 10: 1881\u20131886.","journal-title":"Protein Science"},{"key":"1355_CR12","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1002\/prot.20124","volume":"56","author":"ES Shih","year":"2004","unstructured":"Shih ES, Hwang MJ: Alternative Alignments from Comparison of Protein Structures. PROTEINS: Structure, Function, and Bioinformatics 2004, 56: 519\u2013527.","journal-title":"PROTEINS: Structure, Function, and Bioinformatics"},{"issue":"5","key":"1355_CR13","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1109\/34.6778","volume":"10","author":"S Umeyama","year":"1988","unstructured":"Umeyama S: An eigendecomposition approach to weighted graph matching problems. IEEE transactions on pattern analysis and machine intelligence 1988, 10(5):695\u2013703.","journal-title":"IEEE transactions on pattern analysis and machine intelligence"},{"key":"1355_CR14","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1002\/1097-0134(20001001)41:1<108::AID-PROT130>3.0.CO;2-S","volume":"41","author":"T Kawabata","year":"2000","unstructured":"Kawabata T, Nishikawa K: Protein Structure Comparison Using the Markov Transition Model of Evolution. Proteins 2000, 41: 108\u2013122.","journal-title":"Proteins"},{"key":"1355_CR15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719604","volume-title":"LAPACK Users' Guide","author":"E Anderson","year":"1999","unstructured":"Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J, Du Croz J, Greenbaum A, Hammarling S, McKenney A, Sorensen D: LAPACK Users' Guide. third edition. Philadelphia, PA: Society for Industrial and Applied Mathematics; 1999.","edition":"third"},{"key":"1355_CR16","unstructured":"Rasmol: Molecular Graphics Visualisation Tool[http:\/\/www.openrasmol.org]"},{"key":"1355_CR17","first-page":"300","volume-title":"Pacific Symp on Biocomputing","author":"D Fischer","year":"1996","unstructured":"Fischer D, Elofsson A, Rice DW, Eisenberg D: Assessing the Performance of Fold Recognition Methods By Means of a Comprehensive Benchmark. Pacific Symp on Biocomputing 1996, 300\u2013318."},{"key":"1355_CR18","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/prot.10553","volume":"54","author":"M Novotny","year":"2004","unstructured":"Novotny M, Madsen D, Kleywegt GJ: Evaluation of Protein Fold Comparison Servers. Proteins 2004, 54: 260\u2013270.","journal-title":"Proteins"},{"key":"1355_CR19","first-page":"536","volume":"247","author":"AG Murzin","year":"1995","unstructured":"Murzin AG, Brenner SE, Hubbard T, Chothia C: SCOP: a structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology 1995, 247: 536\u2013540.","journal-title":"Journal of Molecular Biology"},{"key":"1355_CR20","doi-asserted-by":"publisher","first-page":"D189","DOI":"10.1093\/nar\/gkh034","volume":"32","author":"JM Chandonia","year":"2004","unstructured":"Chandonia JM, Hon G, Walker NS, Conte LL, Koehl P, Levitt M, Brenner SE: The ASTRAL compendium in 2004. Nucleic Acids Research 2004, 32: D189-D192.","journal-title":"Nucleic Acids Research"},{"issue":"33","key":"1355_CR21","doi-asserted-by":"publisher","first-page":"12201","DOI":"10.1073\/pnas.0404383101","volume":"101","author":"R Kolodny","year":"2004","unstructured":"Kolodny R, Linial N: Approximate protein structural alignment in polynomial time. Proc Natl Acad SciUSA 2004, 101(33):12201\u201312206.","journal-title":"Proc Natl Acad SciUSA"},{"issue":"6","key":"1355_CR22","first-page":"587","volume":"10","author":"A Godzik","year":"1994","unstructured":"Godzik A, Skolnick J: Flexible algorithm for direct multiple alignment of protein structures and sequences. CABIOS 1994, 10(6):587\u2013596.","journal-title":"CABIOS"},{"key":"1355_CR23","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1089\/106652704773416876","volume":"11","author":"A Caprara","year":"2004","unstructured":"Caprara A, Carr R, Istrail S, Lancia G, Walenz B: 1001 Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap. Journal of Computational Biology 2004, 11: 27\u201352.","journal-title":"Journal of Computational Biology"},{"issue":"5","key":"1355_CR24","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1089\/106652701446152","volume":"7","author":"I Eidhammer","year":"2000","unstructured":"Eidhammer I, Jonassen I, Taylor WR: Structure Comparison and Structure Patterns. Journal of Computational Biology 2000, 7(5):685\u2013716.","journal-title":"Journal of Computational Biology"},{"key":"1355_CR25","volume-title":"A new O(N2) algorithm for the symmetric tridiagonal eigenvalue\/eigenvector problem","author":"IS Dhillon","year":"1997","unstructured":"Dhillon IS: A new O ( N\n                    2\n                  ) algorithm for the symmetric tridiagonal eigenvalue\/eigenvector problem. PhD thesis, Computer Science, University of California, Berkeley; 1997."},{"key":"1355_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M: The identification of common molecular subsequences. Journal of Molecular Biology 1981, 147: 195\u2013197.","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"1355_CR27","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1364\/JOSAA.4.000629","volume":"4","author":"BKP Horn","year":"1987","unstructured":"Horn BKP: Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America 1987, 4(4):629\u2013642.","journal-title":"Journal of the Optical Society of America"},{"key":"1355_CR28","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/(SICI)1097-0134(19981001)33:1<88::AID-PROT8>3.0.CO;2-H","volume":"33","author":"L Holm","year":"1998","unstructured":"Holm L, Sander C: Dictionary of recurrent domains in protein structures. Proteins 1998, 33: 88\u201396.","journal-title":"Proteins"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S5-S5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-7-S5-S5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S5-S5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T02:28:02Z","timestamp":1630463282000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-7-S5-S5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":28,"journal-issue":{"issue":"S5","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["1355"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-7-s5-s5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"18 December 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S5"}}