g_permute: Permutation-reduced phase space density compaction

Biomolecular processes are governed by free energy changes and thus depend on a fine-tuned interplay between entropy and enthalpy. To calculate accurate values for entropies from simulations is particularly challenging for the solvation shell of proteins, which contributes crucially to the total entropy of solvated proteins, due to the diffusive motion of the solvent molecules. Accordingly, for each frame of a Molecular dynamics (MD) trajectory, our software relabels the solvent molecules, such that the resulting configuration space volume is reduced by a factor of N! with N   being the number of solvent molecules. The combinatorial explosion of a naive implementation is here overcome by transforming the task into a linear assignment problem, for which algorithms with complexity O(N3)O(N3) exist. We have shown in previous research that the solvent entropy can be estimated from such a compacted trajectory by established entropy estimation methods. In this paper, we describe the software implementation which also allows applications beyond entropy estimation, such as the permutation of lipids in membrane bilayers.Program summaryProgram title: g_permuteCatalogue identifier: AECJ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECJ_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GPLNo. of lines in distributed program, including test data, etc.: 45 173No. of bytes in distributed program, including test data, etc.: 2 730 678Distribution format: tar.gzProgramming language: CComputer: PC-compatible running LinuxOperating system: LinuxRAM: Dependent on the number of solvent molecules, min 12 582 912 bytesClassification: 3, 4.8, 4.9External routines: liblap (included); From GROMACS-3.3.1: libgmx (not included)Nature of problem: Estimating the entropy of solvent molecules from a molecular dynamics simulation trajectory cannot be performed on ordinary trajectories.Solution method: Compacting the configuration space of molecules by exploiting their permutation symmetry. Applies to trajectories either compatible to those obtained with the GROMACS simulation package [1] or multi-model pdb (Protein Data Bank) files.Restrictions: In rare cases the time to find a solution for the linear assignment problem can be very long.Running time: Dependent on trajectory length and number of molecules to be permuted.References:[1] D. van der Spoel, et al., J. Comput. Chem. 26 (2005) 1701.