{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T22:05:54Z","timestamp":1758405954894},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Protein structure alignment is one of the most important computational problems in molecular biology and plays a key role in protein structure prediction, fold family classification, motif finding, phylogenetic tree reconstruction and so on. From the viewpoint of computational complexity, a pairwise structure alignment is also a NP-hard problem, in contrast to the polynomial time algorithm for a pairwise sequence alignment.<\/jats:p>\n               <jats:p>Results: We propose a method for solving the structure alignment problem in an accurate manner at the amino acid level, based on a mean field annealing technique. We define the structure alignment as a mixed integer-programming (MIP) problem. By avoiding complicated combinatorial computation and exploiting the special structure of the continuous partial problem, we transform the MIP into a reduced non-linear continuous optimization problem (NCOP) with a much simpler form. To optimize the reduced NCOP, a mean field annealing procedure is adopted with a modified Potts model, whose solution is generally identical to that of the MIP. There is no \u2018soft constraint\u2019 in our mean field model and all constraints are automatically satisfied throughout the annealing process, thereby not only making the optimization more efficient but also eliminating many unnecessary parameters that depend on problems and usually require careful tuning. A number of benchmark examples are tested by the proposed method with comparisons to several existing approaches.<\/jats:p>\n               <jats:p>Contact: \u00a0chen@elec.osaka-sandai.ac.jp<\/jats:p>","DOI":"10.1093\/bioinformatics\/bth467","type":"journal-article","created":{"date-parts":[[2004,8,13]],"date-time":"2004-08-13T00:15:36Z","timestamp":1092356136000},"page":"51-62","source":"Crossref","is-referenced-by-count":27,"title":["Protein structure alignment by deterministic annealing"],"prefix":"10.1093","volume":"21","author":[{"given":"Luonan","family":"Chen","sequence":"first","affiliation":[]},{"given":"Tianshou","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Yun","family":"Tang","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2004,8,12]]},"reference":[{"key":"2023013107192588900_B1","doi-asserted-by":"crossref","unstructured":"Arun, K.S., Huang, T.S., Blostein, S.D. 1987Least-squares fitting of two 3-D point sets. IEEE Trans. Pattern Anal. Machine Intell.PAMI-9698\u2013701","DOI":"10.1109\/TPAMI.1987.4767965"},{"key":"2023013107192588900_B2","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M. Nonlinear Programming: Theory and Algorithms1993 2nd edn , New York  Wiley"},{"key":"2023013107192588900_B3","doi-asserted-by":"crossref","unstructured":"Blankenbecler, R., Ohlsson, M., Peterson, C., Ringner, M. 2003Matching protein structures with fuzzy alignments. Proc. Natl Acad. Sci. USA100,  pp. 11936\u201311940","DOI":"10.1073\/pnas.1635048100"},{"key":"2023013107192588900_B4","unstructured":"Bryant, S.H. and Altschul, S.F. 1995Statistics of sequence\u2013structure threading. Curr. Opin. Struct. Biol.5236\u2013244"},{"key":"2023013107192588900_B5","doi-asserted-by":"crossref","unstructured":"Chen, L. and Aihara, K. 1995Chaotic simulated annealing by a neural network model with transient chaos. Neural Networks8915\u2013930","DOI":"10.1016\/0893-6080(95)00033-V"},{"key":"2023013107192588900_B6","unstructured":"Chen, L. and Aihara, K. 1999Global searching ability of chaotic neural networks. IEEE Trans. Circuits Syst.46974\u2013993"},{"key":"2023013107192588900_B7","unstructured":"Gerstein, M. and Levitt, M. 1996Using iterative dynamic programming to obtain accurate pairwise and multiple alignments of protein structures. Proceedings of the Fourth International Conference on Intelligent Systems in Molecular Biology (ISMB) June 12\u201315, , IL  St Louis,  pp. 59\u201367"},{"key":"2023013107192588900_B8","unstructured":"Higham, N.J. 1986Newton's method for the matrix square root. Math. Comput.46537\u2013549"},{"key":"2023013107192588900_B9","doi-asserted-by":"crossref","unstructured":"Hiroike, T. and Toh, H. 2001A local structural alignment method that accommodates with circular permutation. Chem-Bio Inform. J.1103\u2013114","DOI":"10.1273\/cbij.1.103"},{"key":"2023013107192588900_B10","unstructured":"Holm, L. and Sander, C. 1993Protein structure comparison by alignment of distance matrices. J. Mol. Biol.233123\u2013138"},{"key":"2023013107192588900_B11","unstructured":"Ishii, S. and Sato, M. 2002Doubly constrained network for combinatorial optimization. Neurocomputing43239\u2013257"},{"key":"2023013107192588900_B12","unstructured":"Luenberger, D.G. Linear and Nonlinear Programming2003 2nd edn  Kluwer Academic Publishers"},{"key":"2023013107192588900_B13","doi-asserted-by":"crossref","unstructured":"Mizuguchi, K., Deane, C.M., Blundell, T.L., Overington, J.P. 1998HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci.7,  pp. 2469\u20132471","DOI":"10.1002\/pro.5560071126"},{"key":"2023013107192588900_B14","unstructured":"Mount, DW. Bioinformatics2001, Cold Spring Harbor, New York  Cold Spring Harbor Laboratory Press"},{"key":"2023013107192588900_B15","doi-asserted-by":"crossref","unstructured":"Needleman, S.B. and Wunsch, C.D. 1971A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol.48,  pp. 443\u2013453","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"2023013107192588900_B16","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L. and Wolsey, L.A. Integer and Combinatorial Optimization1988, New York  Wiley","DOI":"10.1002\/9781118627372"},{"key":"2023013107192588900_B17","unstructured":"Ohlsson, M., Peterson, C., Ringner, M., Blankenbecler, R. 2000A Novel Approach to Structure Alignment. Protein Sci.7,  pp. 445\u2013456"},{"key":"2023013107192588900_B18","doi-asserted-by":"crossref","unstructured":"Orengo, C.A. and Taylor, W.R. 1996SSAP: sequential structure alignment program for protein structure comparison. Methods Enzymol.266617\u2013635","DOI":"10.1016\/S0076-6879(96)66038-8"},{"key":"2023013107192588900_B19","unstructured":"Peterson, C. and Anderson, J.R. 1987A mean field theory learning algorithm for neural networks. Complex Syst.1995\u20131019"},{"key":"2023013107192588900_B20","doi-asserted-by":"crossref","unstructured":"Peterson, C. and Soderberg, B. 1989A new method for mapping optimization problems onto neural networks. Int. J. Neural Syst.13\u201322","DOI":"10.1142\/S0129065789000414"},{"key":"2023013107192588900_B21","doi-asserted-by":"crossref","unstructured":"Shindyalov, I. and Bourne, P. 1998Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng.11739\u2013747","DOI":"10.1093\/protein\/11.9.739"},{"key":"2023013107192588900_B22","unstructured":"Szustakowski, J. and Weng, Z. 2000Structural alignment using a genetic algorithm. Prot. Struct. Funct. Genet.38438\u2013440"},{"key":"2023013107192588900_B23","doi-asserted-by":"crossref","unstructured":"Uliel, S., Fliess, A., Amir, A., Unger, R. 1999A simple algorithm for detecting circular permutations in proteins. Bioinformatics15930\u2013936","DOI":"10.1093\/bioinformatics\/15.11.930"},{"key":"2023013107192588900_B24","unstructured":"Urahama, K. 1994Analog method for solving combinatorial optimization problems. IEICE Trans. Inform. Syst.E77-A302\u2013308"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/1\/51\/48961809\/bioinformatics_21_1_51.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/1\/51\/48961809\/bioinformatics_21_1_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T09:56:11Z","timestamp":1675158971000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/1\/51\/212513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8,12]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bth467","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,1,1]]},"published":{"date-parts":[[2004,8,12]]}}}