Engler Martin S, Caron Bertrand, Veen Lourens, Geerke Daan P, Mark Alan E, Klau Gunnar W
1Algorithmic Bioinformatics, Heinrich Heine University, Universitätsstr. 1, 40225 Düsseldorf, Germany.
2Life Sciences and Health Group, Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, The Netherlands.
Algorithms Mol Biol. 2019 Feb 5;14:1. doi: 10.1186/s13015-019-0138-7. eCollection 2019.
A key factor in computational drug design is the consistency and reliability with which intermolecular interactions between a wide variety of molecules can be described. Here we present a procedure to efficiently, reliably and automatically assign partial atomic charges to atoms based on known distributions. We formally introduce the molecular charge assignment problem, where the task is to select a charge from a set of candidate charges for every atom of a given query molecule. Charges are accompanied by a score that depends on their observed frequency in similar neighbourhoods (chemical environments) in a database of previously parameterised molecules. The aim is to assign the charges such that the total charge equals a known target charge within a margin of error while maximizing the sum of the charge scores. We show that the problem is a variant of the well-studied multiple-choice knapsack problem and thus weakly -complete. We propose solutions based on Integer Linear Programming and a pseudo-polynomial time Dynamic Programming algorithm. We demonstrate that the results obtained for novel molecules not included in the database are comparable to the ones obtained performing explicit charge calculations while decreasing the time to determine partial charges for a molecule from hours or even days to below a second. Our software is openly available.
计算药物设计中的一个关键因素是能否一致且可靠地描述各种分子之间的分子间相互作用。在此，我们提出一种基于已知分布为原子高效、可靠且自动地分配部分原子电荷的方法。我们正式引入分子电荷分配问题，其任务是为给定查询分子的每个原子从一组候选电荷中选择一个电荷。电荷伴随着一个分数，该分数取决于它们在先前参数化分子数据库中相似邻域（化学环境）中的观察频率。目标是分配电荷，使得总电荷在误差范围内等于已知目标电荷，同时使电荷分数的总和最大化。我们表明该问题是经过充分研究的多选择背包问题的一个变体，因此是弱NP完全问题。我们提出基于整数线性规划和伪多项式时间动态规划算法的解决方案。我们证明，对于数据库中未包含的新分子所获得的结果，与进行显式电荷计算所获得的结果相当，同时将确定一个分子部分电荷的时间从数小时甚至数天减少到不到一秒。我们的软件可公开获取。
