TY - JOUR
T1 - Automated partial atomic charge assignment for drug-like molecules
T2 - A fast knapsack approach
AU - Engler, Martin S.
AU - Caron, Bertrand
AU - Veen, Lourens
AU - Geerke, Daan P.
AU - Mark, Alan E.
AU - Klau, Gunnar W.
PY - 2019/2/5
Y1 - 2019/2/5
N2 - 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 \mathcal {NP} NP -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.
AB - 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 \mathcal {NP} NP -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.
KW - Integer Linear Programming
KW - Molecular dynamics simulations
KW - Multiple-choice knapsack
KW - Partial charge assignment
KW - Pseudo-polynomial Dynamic Programming
UR - http://www.scopus.com/inward/record.url?scp=85061137552&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061137552&partnerID=8YFLogxK
U2 - 10.1186/s13015-019-0138-7
DO - 10.1186/s13015-019-0138-7
M3 - Article
AN - SCOPUS:85061137552
VL - 14
SP - 1
EP - 10
JO - Algorithms for Molecular Biology
JF - Algorithms for Molecular Biology
SN - 1748-7188
IS - 1
M1 - 1
ER -