  


A Linear Programming Approach for the LeastSquares Protein Morphing Problem
Mihai Anitescu(anitescumcs.anl.gov) Abstract: This work addresses the computation of freeenergy differences 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 freeenergy computation, we seek to find the per mutation \sigma that minimizes the meansquare 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 Birkhoff'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 signicantly improves the efficiency of the freeenergy computation. Keywords: Linear programming,linear assignment problems, Birkhoff's theorem, protein conformations, freeenergy 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/MCSP15420908, Argonne National Laboratory, Argonne, IL, 60439, September 2008 Download: [PDF] Entry Submitted: 09/26/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  