WaterAlignment: Identification of displaced water molecules in molecular docking using Jonker and Volgenant shortest path augmentation for linear assignment

Abstract The dynamics of individual water molecules has a strong effect on the energetics of biochemical interactions, such as peptide-protein binding. Existing software are able to predict the location of water molecules at the interface between a macromolecule and a ligand in a single state or at a particular time point. The program described in this article compares explicit solvent molecules from two different states within a given volume of space; for example between a free protein versus the same protein with a ligand bound. This comparison creates a unique one-to-one matching between waters from the two states utilizing the Jonker and Volgenant algorithm for linear assignment. Matchings are deterministic and minimize the sum of the distance between matched pairs. Explicit solvent ligand docking can utilize this matching to understand how ligand binding affects the energy of interface waters. This algorithm can also be used to compare predicted water molecules to those seen in X-ray crystallography, or to compare two different methods of solvent prediction. Program summary Program title: WaterAlignment Program files doi: http://dx.doi.org/10.17632/pk6fnvwgg7.1 Licensing provisions: GNU Lesser General Public License Programming language: Python Nature of problem: Comparison of the location of solvent water molecules present in the same volume under two conditions in order to ‘match’ waters between the two conditions; that is, to define matched waters that represent the same molecule. The algorithm was developed to compare waters present in the binding pocket of a protein with and without a bound ligand, in order to determine the effect of ligand binding on the energy of waters in the binding pocket. Solution method: The task is treated as a linear assignment problem solved by the Jonker and Volgenant algorithm. A bipartite graph is constructed with each part of the graph consisting of nodes representing one of the two set of waters. Edges facing from the first set of nodes to the second set are added with cost equal to the distance between the waters that the nodes represent. This data structure is then used to create propositional matches, with each new match able to replace prior matches when beneficial to the overall result.