Optimal drug combinations and minimal hitting sets

Abstract

Background: Identifying effective drug combinations that significantly improve over single agents is a challenging problem. Pairwise combinations already represent a huge screening effort. Beyond two drug combinations the task seems unfeasible.

Results: In this work we introduce a method to uncover drug combinations with a putative effective response when presented to a heterogeneous population of malignant agents (strains), such as cancer cell lines or viruses. Using data quantifying the effect of single drugs over several individual strains, we search for minimal drug combinations that successfully target all strains. We show that the latter problem can be mapped to a minimal hitting set problem in mathematics. We illustrate this approach using data for the NCI60 panel of tumor derived cell lines, uncovering 14 anticancer drug combinations.

Conclusion: The drug-response graph and the associated minimal hitting set method can be used to uncover effective drug combinations in anticancer drug screens and drug development programs targeting heterogeneous populations of infectious agents such as HIV.

Figure 1

Strain-drug response graph and the hitting set problem. A strain-drug response graph with squares representing strains, circles representing drugs, and edges representing a good response of the strain at one end to the drug at the other end. Covered circles represent drugs that are in our cocktail and empty those that are not.

Figure 2

NCI60 case study. a) Distribution of the normalized IC50 for three different chemical agents (bars) and the same distribution for all (cell line, drug) pairs (solid line). Δlog₁₀IC50 denotes the log₁₀IC50 change relative to the drug dependent mean over all cell lines. s denotes the standard deviation of Δlog₁₀IC50 over all (cell line, drug) pairs. The dashed line marks the threshold at two standard deviations above the mean. b) The fraction p_k of drugs connected to k strains in the NCI60 strain-drug response graph (symbols). The solid line represents the best fit to an exponential decay. c) Graphical representation of the minimal hitting set number 1 in Table 1.

Figure 3

Minimal hitting sets for incomplete drug-response graphs. When information about the response of some strains to some drugs is unavailable the strain-drug response graph is incomplete. This could result in an overestimate of the size of the minimal hitting set. a) For example, if the response of strain 3 to drug 1 has not been tested, and the corresponding edge is missing (dashed line), we will be force to cover drug 2. This will increase the minimal hitting set size from 2 to 3 drugs. b) Estimated minimal hitting set size of the NCI60 strain-drug response graph, after assuming that only a certain fraction of the interactions were tested. Note that data for 10% of the strain-drug pairs was already missing from the original dataset and, therefore, we cannot go beyond 90%. The dashed-dotted, solid and dashed line represent the minimum, average and maximum minimal hitting set sizes over 100 incomplete strain-drug response graphs. For each graph the minimal hitting set was estimated using 100 runs of the highest-degree-first algorithm.