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.
Citation
Preprint ANL/MCS-P1542-0908, Argonne National Laboratory, Argonne, IL, 60439, September 2008