Automated partial atomic charge assignment for drug-like molecules: A fast knapsack approach

Martin S. Engler, Bertrand Caron, Lourens Veen, Daan P. Geerke, Alan E. Mark, Gunnar W. Klau

Research output: Contribution to JournalArticleAcademicpeer-review

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 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.

Original languageEnglish
Article number1
Pages (from-to)1-10
Number of pages10
JournalAlgorithms for Molecular Biology
Volume14
Issue number1
DOIs
Publication statusPublished - 5 Feb 2019

Fingerprint

Knapsack
Drugs
Assignment
Charge
Molecules
Databases
Linear Programming
Partial
Drug Design
Pharmaceutical Preparations
Software
Atoms
Dynamic programming
Linear programming
Assign
Polynomials
Integer Linear Programming
Knapsack Problem
Assignment Problem
Margin

Keywords

  • Integer Linear Programming
  • Molecular dynamics simulations
  • Multiple-choice knapsack
  • Partial charge assignment
  • Pseudo-polynomial Dynamic Programming

Cite this

Engler, Martin S. ; Caron, Bertrand ; Veen, Lourens ; Geerke, Daan P. ; Mark, Alan E. ; Klau, Gunnar W. / Automated partial atomic charge assignment for drug-like molecules : A fast knapsack approach. In: Algorithms for Molecular Biology. 2019 ; Vol. 14, No. 1. pp. 1-10.
@article{aa8430518dee46f28f2611eb4c3b886d,
title = "Automated partial atomic charge assignment for drug-like molecules: A fast knapsack approach",
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 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.",
keywords = "Integer Linear Programming, Molecular dynamics simulations, Multiple-choice knapsack, Partial charge assignment, Pseudo-polynomial Dynamic Programming",
author = "Engler, {Martin S.} and Bertrand Caron and Lourens Veen and Geerke, {Daan P.} and Mark, {Alan E.} and Klau, {Gunnar W.}",
year = "2019",
month = "2",
day = "5",
doi = "10.1186/s13015-019-0138-7",
language = "English",
volume = "14",
pages = "1--10",
journal = "Algorithms for Molecular Biology",
issn = "1748-7188",
publisher = "BioMed Central",
number = "1",

}

Automated partial atomic charge assignment for drug-like molecules : A fast knapsack approach. / Engler, Martin S.; Caron, Bertrand; Veen, Lourens; Geerke, Daan P.; Mark, Alan E.; Klau, Gunnar W.

In: Algorithms for Molecular Biology, Vol. 14, No. 1, 1, 05.02.2019, p. 1-10.

Research output: Contribution to JournalArticleAcademicpeer-review

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

VL - 14

SP - 1

EP - 10

JO - Algorithms for Molecular Biology

JF - Algorithms for Molecular Biology

SN - 1748-7188

IS - 1

M1 - 1

ER -