Optimization Online


Continuous Optimization Methods for Structure Alignments

Roberto Andreani (andreani***at***ime.unicamp.br)
José Mario Martínez (martinez***at***ime.unicamp.br )
Leandro Martínez (lmartinez***at***iqm.unicamp.br)
Flavio Yano (yano***at***ime.unicamp.br)

Abstract: 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.

Keywords: Structural alignment, Protein alignment, Gauss-Newton method, Continuous optimization, Order-Value Optimization

Category 1: Nonlinear Optimization

Category 2: Applications -- Science and Engineering (Basic Sciences Applications )

Citation: To appear in Mathematical Programming
web: http://www.ime.unicamp.br/~martinez/lovoalign

Download: [PDF]

Entry Submitted: 01/30/2006
Entry Accepted: 01/30/2006
Entry Last Modified: 06/02/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society