Canzar Stefan, El-Kebir Mohammed, Pool René, Elbassioni Khaled, Mark Alan E, Geerke Daan P, Stougie Leen, Klau Gunnar W
Centrum Wiskunde & Informatica, Life Sciences Group, Amsterdam, The Netherlands.
J Comput Biol. 2013 Mar;20(3):188-98. doi: 10.1089/cmb.2012.0239.
Molecular simulation techniques are increasingly being used to study biomolecular systems at an atomic level. Such simulations rely on empirical force fields to represent the intermolecular interactions. There are many different force fields available--each based on a different set of assumptions and thus requiring different parametrization procedures. Recently, efforts have been made to fully automate the assignment of force-field parameters, including atomic partial charges, for novel molecules. In this work, we focus on a problem arising in the automated parametrization of molecules for use in combination with the GROMOS family of force fields: namely, the assignment of atoms to charge groups such that for every charge group the sum of the partial charges is ideally equal to its formal charge. In addition, charge groups are required to have size at most k. We show NP-hardness and give an exact algorithm that solves practical problem instances to provable optimality in a fraction of a second.
分子模拟技术越来越多地被用于在原子水平上研究生物分子系统。此类模拟依赖于经验力场来表示分子间相互作用。有许多不同的力场可供使用——每个力场都基于不同的假设集，因此需要不同的参数化程序。最近，人们努力实现力场参数（包括原子部分电荷）分配的完全自动化，以用于新分子。在这项工作中，我们关注在与GROMOS力场家族结合使用的分子自动参数化过程中出现的一个问题：即，将原子分配到电荷组，使得对于每个电荷组，部分电荷的总和理想情况下等于其形式电荷。此外，电荷组的大小要求至多为k。我们证明了该问题的NP难性质，并给出了一种精确算法，该算法能在几分之一秒内将实际问题实例求解到可证明的最优解。
