Combinatorial therapy discovery using mixed integer linear programming

Abstract

Motivation: Combinatorial therapies play increasingly important roles in combating complex diseases. Owing to the huge cost associated with experimental methods in identifying optimal drug combinations, computational approaches can provide a guide to limit the search space and reduce cost. However, few computational approaches have been developed for this purpose, and thus there is a great need of new algorithms for drug combination prediction.

Results: Here we proposed to formulate the optimal combinatorial therapy problem into two complementary mathematical algorithms, Balanced Target Set Cover (BTSC) and Minimum Off-Target Set Cover (MOTSC). Given a disease gene set, BTSC seeks a balanced solution that maximizes the coverage on the disease genes and minimizes the off-target hits at the same time. MOTSC seeks a full coverage on the disease gene set while minimizing the off-target set. Through simulation, both BTSC and MOTSC demonstrated a much faster running time over exhaustive search with the same accuracy. When applied to real disease gene sets, our algorithms not only identified known drug combinations, but also predicted novel drug combinations that are worth further testing. In addition, we developed a web-based tool to allow users to iteratively search for optimal drug combinations given a user-defined gene set.

Availability: Our tool is freely available for noncommercial use at http://www.drug.liuzlab.org/.

Contact: zhandong.liu@bcm.edu

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Running time difference between BTSC and ES. The number of associated drugs is simulated from 10 to 30 with a step size equal to 2. Each data point represents the average running time of 10 replicates. For the simulated data with 30 associated drugs, ES takes ∼4.7 days, whereas BTSC needs only 9 s

Fig. 2.

The disease–gene–drug network of AMI. The disease gene set name AMI is represented using a cyan hexagon, and there are 20 genes (red, orange or chocolate circles) in the AMI gene set. Four (green squares) of 35 associated drugs (green or gray squares) selected by BTSC can cover seven AMI genes (red circles) with no known off-target. Eight genes (orange circles) have no associated drugs, and five genes (chocolate circles) associated with drugs are not covered by the selected drug combination

Fig. 3.

The disease–gene–drug network of EPAM. The disease gene set name EPAM is represented using a cyan hexagon, and there are 18 genes (red, orange or chocolate circles) in the EPAM gene set. Five (green squares) of 41 associated drugs (green or gray squares) selected by BTSC can cover 10 EPAM genes (red circles) with no known off-target. Six genes (orange circles) have no associated drugs, and two genes (chocolate circles) associated with drugs are not covered by the selected drug combination

Fig. 4.

The disease–gene–drug network of HTN. The disease gene set name HTN is represented using a cyan hexagon, and there are 26 genes (red, orange or chocolate circles) in the HTN gene set. Five (green squares) of 77 associated drugs (green or gray squares) selected by BTSC can cover 10 HTN genes (red circles) with only one off-target (blue circle). Seven genes (orange circles) have no associated drugs, and nine genes (chocolate circles) associated with drugs are not covered by the selected drug combination