This work addresses the computation of free-energy 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 free-energy computation, we seek to find 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 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 free-energy computation.
Preprint ANL/MCS-P1542-0908, Argonne National Laboratory, Argonne, IL, 60439, September 2008