Optimization Online


A Linear Programming Approach for the Least-Squares Protein Morphing Problem

Mihai Anitescu(anitescu***at***mcs.anl.gov)
Sanghyun Park(sanghyun***at***mcs.anl.gov)

Abstract: This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom n into atom n. Because shorter morphing paths reduce the cost of the free-energy computation, we seek to fi nd the per- mutation \sigma that minimizes the mean-square distance traveled by the atoms. Instead of performing this combinatorial search in the space of permutations, we relax the search onto the space of bistochastic matrices and solve the re- laxed problem by linear programming. Using Birkho ff's theorem, we show that the solution of the relaxed problem is indeed identical to the solution of the original problem. We demonstrate that the use of such optimal permu- tations signi cantly improves the efficiency of the free-energy computation.

Keywords: Linear programming,linear assignment problems, Birkhoff 's theorem, protein conformations, free-energy calculation

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

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

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: Preprint ANL/MCS-P1542-0908, Argonne National Laboratory, Argonne, IL, 60439, September 2008

Download: [PDF]

Entry Submitted: 09/26/2008
Entry Accepted: 09/26/2008
Entry Last Modified: 09/26/2008

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