Structural Alignment is an important tool for fold identification of proteins, structural screening on ligand databases, pharmacophore identification and other applications. In the general case, the optimization problem of superimposing two structures is nonsmooth and nonconvex, so that most popular methods are heuristic and do not employ derivative information. Usually, these methods do not admit convergence theories of practical significance. In this work it is shown that the optimization of the superposition of two structures may be addressed using continuous smooth minimization. It is proved that, using a Low Order-Value Optimization approach, the nonsmoothness may be essentially ignored and classical optimization algorithms may be used. Within this context, a Gauss-Newton method is introduced for structural alignments incorporating (or not) transformations (as flexibility) on the structures. Convergence theorems are provided and practical aspects of implementation are described. Numerical experiments suggest that the Gauss-Newton methodology is competitive with state-of-the-art algorithms for protein alignment both in terms of quality and speed. Additional experiments on binding site identification, ligand and cofactor alignments illustrate the generality of this approach. The softwares containing the methods presented here are available at http://www.ime.unicamp. br/~martinez/lovoalign. © 2007 Springer-Verlag.112193124Andreani, R., Dunder, C., Martínez, J.M., Order-Value Optimization: Formulation and solution by means of a primal Cauchy method (2003) Math. Methods Oper. Res., 58, pp. 387-399Andreani, R., Martínez, J.M., Martínez, L., Yano, F., Low order-value optimization and applications (2005) Technical Report, MCDO 051013. , Department of Applied Mathematics, State University of Campinas, BrazilAndreani, R., Martínez, J.M., Salvatierra, M., Yano, F., Quasi-Newton methods for order-value optimization and value-at-risk calculations (2006) Pac. J. Optim., 2, pp. 11-33Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H., Shindyalov, I.N., Bourne, P.E., The protein data bank (2000) Nucleic Acids Res., 28, pp. 235-242Brinkmann, G., Dress, A.W.M., Perrey, S.W., Stoye, J., Two applications of the Divide & Conquer principle in the molecular sciences (1997) Math. Program., 79, pp. 71-97Chreneik, J.E., Burgin, A.B., Pommier, Y., Stewart, L., Redinbo, M.R., Structural impact of the Leukemia Drug 1-Beta-D-Arabinofuranosyleytosine (Ara-C) on the Covalent Human Topoisomerase I-DNA Complex (2003) J. Biol. Chem, 278, pp. 12461-12466Gerstein, M., Levitt, M., Comprehensive assessment of automatic structural alignment against a manual standard, the Scop classification of proteins (1998) Protein Sci., 7, pp. 445-456Golub, G.H., Van Loan, Ch.F., (1983) Matrix Computations, , Johns Hopkins BaltimoreHolm, L., Park, J., DaliLite workbench for protein structure comparison (2000) Bioinformatics, 16, pp. 566-567Holm, L., Sander, C., Protein structure comparison by alignment of distance matrices (1993) J. Mol. Biol., 233, pp. 123-138Holm, L., Sander, C., Mapping the protein universe (1996) Science, 273, pp. 595-602Kabsch, W., A discussion of the solution for the best rotation to relate two sets of vectors (1978) Acta Crystallog. A, 34, pp. 827-828Kearsley, S.K., On the orthogonal transformation used for structural comparisons (1989) Acta Crystallog. A, 45, pp. 208-210Kedem, K., Chew, L.P., Elber, R., Unit-vector RMS (URMS) as a tool to analyze molecular dynamics trajectories (1999) Proteins, 37, pp. 554-564Kleywegt, G.J., Use of non-crystallographic symmetry in protein structure refinement (1996) Acta Crystallog. D, 52, pp. 842-857Kolodny, R., Koehl, P., Levitt, M., Comprehensive evaluation of protein structure alignment methods: Scoring by geometric measures (2005) J. Mol. Biol., 346, pp. 1173-1188Kolodny, R., Linial, N., Approximate protein structural alignment in polynomial time (2004) P. Natl. Acad. Sci. USA, 101, pp. 12201-12206Krissinel, E., Henrick, K., Protein structure comparison in 3D based on secondary structure matching (SSM) followed by C-alpha alignment, scored by a new structural similarity function (2003) Proceedings of the First International Conference on Molecular Structural Biology, , [Kungl, A.J., Kungl, P.J. (eds.)] Vienna, September 3-7Krissinel, E., Henrick, K., Secondary-structure matching (SSM), a new tool for fast protein structure alignment in three dimensions (2004) Acta Crystallog. D, 60, pp. 2256-2268Lupyan, D., Leo-Macias, A., Ortiz, A.R., A new progressive-iterative algorithm for multiple structure alignment (2005) Bioinformatics, 21, pp. 3255-3263Needleman, B., Wounsch, C.D., A general method applicable to the search for similarities in the amino acid sequence of two proteins (1970) J. Mol. Biol., 48, pp. 443-453Neubert, K.D., Flashsort1 Algorithm (1998) Dr. Dobb's J., 23, pp. 123-124Nocedal, J., Wright, S.J., (1999) Numerical Optimization, , Springer New YorkNunes, A.M., Aparicio, R., Santos, M.A.M., Portugal, R.V., Dias, S.M.G., Neves, A.R., Simeoni, L.A., Polikarpov, I., Crystallization and preliminary X-ray diffraction studies of isoform alpha 1 of the human thyroid hormone receptor ligand-binding domain (2004) Acta Crystallog. D, 60, pp. 1867-1870Ortiz, A.R., Strauss, C.E., Olmea, O., MAMMOTH (matching molecular models obtained from theory): An automated method for model comparison (2002) Protein Sci., 11, pp. 2606-2621Redinbo, M.R., Stewart, L., Kuhn, P., Champoux, J.J., Hol, W.G.J., Crystal structures of Human Topoisomerase i in covalent and noncovalent complexes with DNA (1998) Science, 279, pp. 1504-1513Sandelin, E., Extracting multiple structural alignments: A comparison of a rigorous and a heuristic approach (2005) Bioinformatics, 21, pp. 1002-1009Shatsky, M., Nussinov, R., Wolfson, H.J., Flexible protein alignment and hinge detection (2002) Proteins, 48, pp. 242-256Shyndialov, I.N., Bourne, P.E., Protein structure alignment by incremental combinatorial extension (CE) of the optimal path (1998) Protein Eng., 1, pp. 739-747Subbiah, S., Laurents, D.V., Levitt, M., Structural similarity of DNA-binding domains of bacteriophage repressors and the globin core (1993) Curr. Biol., 3, pp. 141-148Taylor, W.R., Protein structure alignment using iterated double dynamic programming (1991) Protein Sci., 8, pp. 654-665Taylor, W.R., Orengo, C.A., Protein structure alignment (1989) J. Mol. Biol., 208, pp. 1-22Wagner, R.A., Fischer, M.J., String-to-string correction problem (1974) J. ACM, 21, pp. 168-173Weisstein, E.W., 'Rodrigues' Rotation Formula, , http://mathworld.wolfram.com/RodriguesRotationFormula.htmlYe, Y., Godzik, A., Flexible structure alignment by chaining aligned fragment pairs allowing twists (2003) Bioinformatics, 19, pp. 246-ii255. , Suppl. 2Ye, L., Li, Y.L., Mellstrom, K., Mellin, C., Bladh, L.G., Koehler, K., Garg, N., Malm, J., Thyroid receptor ligands. 1. Agonist ligands selective for the thyroid receptor beta(1) (2003) J. Med. Chem., 46, pp. 1580-1588Zhu, J., Weng, Z., A novel protein structure alignment algorithm (2005) Proteins, 58, pp. 618-627