{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T22:33:13Z","timestamp":1649197993110},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Design of protein structure comparison algorithm is an important research issue, having far reaching implications. In this article, we describe a protein structure comparison scheme, which is capable of detecting correct alignments even in difficult cases, e.g. non-topological similarities. The proposed method computes protein structure alignments by comparing, small substructures, called <jats:italic>neighborhoods<\/jats:italic>. Two different types of neighborhoods, sequence and structure, are defined, and two algorithms arising out of the scheme are detailed. A new method for computing equivalences having non-topological similarities from pairwise similarity score is described. A novel and fast technique for comparing sequence neighborhoods is also developed.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>The experimental results show that the current programs show better performance on Fischer and Novotny's benchmark datasets, than state of the art programs, e.g. DALI, CE and SSM. Our programs were also found to calculate correct alignments for proteins with huge amount of indels and internal repeats. Finally, the sequence neighborhood based program was used in extensive fold and non-topological similarity detection experiments. The accuracy of the fold detection experiments with the new measure of similarity was found to be similar or better than that of the standard algorithm CE.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>A new scheme, resulting in two algorithms, have been developed, implemented and tested. The programs developed are accessible at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/mllab.csa.iisc.ernet.in\/mp2\/runprog.html\" ext-link-type=\"uri\">http:\/\/mllab.csa.iisc.ernet.in\/mp2\/runprog.html<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-8-77","type":"journal-article","created":{"date-parts":[[2007,3,6]],"date-time":"2007-03-06T07:03:31Z","timestamp":1173164611000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Comparison of protein structures by growing neighborhood alignments"],"prefix":"10.1186","volume":"8","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":[[2007,3,6]]},"reference":[{"issue":"5275","key":"1449_CR1","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"},{"key":"1449_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":"1449_CR3","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"},{"key":"1449_CR4","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":"3","key":"1449_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":"1449_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"},{"issue":"9","key":"1449_CR7","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"},{"issue":"12 Part 1","key":"1449_CR8","doi-asserted-by":"publisher","first-page":"2256","DOI":"10.1107\/S0907444904026460","volume":"60","author":"E Krissinel","year":"2004","unstructured":"Krissinel E, Henrick K: Secondary-structure matching (SSM), a new tool for fast protein structure alignment in three dimensions. Acta Crystallographica Section D 2004, 60(12 Part 1):2256\u20132268.","journal-title":"Acta Crystallographica Section D"},{"issue":"5","key":"1449_CR9","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":"1449_CR10","unstructured":"Matchprot: Compare Protein Structures[http:\/\/mllab.csa.iisc.ernet.in\/mp2\/]"},{"key":"1449_CR11","first-page":"300","volume-title":"Assessing the Performance of Fold Recognition Methods By Means of a Comprehensive Benchmark","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.1996, 300\u2013318. [http:\/\/mllab.csa.iisc.ernet.in\/mp2\/]"},{"key":"1449_CR12","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: Structure, Function, and Bioinformatics 2004, 54: 260\u2013270.","journal-title":"PROTEINS: Structure, Function, and Bioinformatics"},{"key":"1449_CR13","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.jmb.2004.12.032","volume":"346","author":"PK Rachel Kolodny","year":"2005","unstructured":"Rachel Kolodny PK, Levitt M: Comprehensive Evaluation of Protein Structure Alignment Methods: Scoring by Geometric Measures. Journal of Molecular Biology 2005, 346: 1173\u20131188.","journal-title":"Journal of Molecular Biology"},{"key":"1449_CR14","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":"1449_CR15","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":"1449_CR16","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"},{"key":"1449_CR17","unstructured":"Rasmol: Molecular Graphics Visualisation Tool[http:\/\/www.openrasmol.org]"},{"issue":"8","key":"1449_CR18","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1016\/S0969-2126(97)00260-8","volume":"5","author":"CA Orengo MAJSJDSM","year":"1997","unstructured":"Orengo MAJSJDSM CA, Thornton J: CATH- A Hierarchic Classification of Protein Domain Structures. Structure 1997, 5(8):1093\u20131108.","journal-title":"Structure"},{"key":"1449_CR19","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":"1449_CR20","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"},{"issue":"33","key":"1449_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. Proceedings of National Academy of Science 2004, 101(33):12201\u201312206.","journal-title":"Proceedings of National Academy of Science"},{"issue":"4","key":"1449_CR22","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":"1449_CR23","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"},{"key":"1449_CR24","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1002\/spe.588","volume":"34","author":"EB Krissinel","year":"2004","unstructured":"Krissinel EB, Henrick K: Common subgraph isomorphism detection by backtracking search. Software \u2013 Practice and Experience 2004, 34: 591\u2013607.","journal-title":"Software \u2013 Practice and Experience"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-77.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:42:38Z","timestamp":1630460558000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3,6]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1449"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-77","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3,6]]},"assertion":[{"value":"12 September 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"77"}}