Engler, Martin S. ;
Caron, Bertrand ;
Veen, Lourens ;
Geerke, Daan P. ;
Mark, Alan E. ;
Klau, Gunnar W.
MultipleChoice Knapsack for Assigning Partial Atomic Charges in DrugLike Molecules
Abstract
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 wellstudied multiplechoice knapsack problem and thus weakly NPcomplete. We propose solutions based on Integer Linear Programming and a pseudopolynomial time Dynamic Programming algorithm. We show 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 by several orders of magnitude, that is, from hours or even days to below a second.
Our software is openly available at https://github.com/enitram/charge_assign.
BibTeX  Entry
@InProceedings{engler_et_al:LIPIcs:2018:9318,
author = {Martin S. Engler and Bertrand Caron and Lourens Veen and Daan P. Geerke and Alan E. Mark and Gunnar W. Klau},
title = {{MultipleChoice Knapsack for Assigning Partial Atomic Charges in DrugLike Molecules}},
booktitle = {18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
pages = {16:116:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770828},
ISSN = {18688969},
year = {2018},
volume = {113},
editor = {Laxmi Parida and Esko Ukkonen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9318},
URN = {urn:nbn:de:0030drops93187},
doi = {10.4230/LIPIcs.WABI.2018.16},
annote = {Keywords: Multiplechoice knapsack, integer linear programming, pseudopolynomial dynamic programming, partial charge assignment, molecular dynamics simulations}
}
2018
Keywords: 

Multiplechoice knapsack, integer linear programming, pseudopolynomial dynamic programming, partial charge assignment, molecular dynamics simulations 
Seminar: 

18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Issue date: 

2018 
Date of publication: 

2018 