Combinatorial therapy discovery using mixed integer linear programming.

Area of Science:

• Computational biology
• Bioinformatics
• Drug discovery

Background:

• Combinatorial therapies are crucial for complex diseases.
• Experimental identification of optimal drug combinations is costly.
• A need exists for advanced computational algorithms for drug combination prediction.

Purpose of the Study:

• To develop novel computational algorithms for predicting optimal drug combinations.
• To address the limitations of current computational approaches in drug combination prediction.

Main Methods:

• Formulated the optimal combinatorial therapy problem using two algorithms: Balanced Target Set Cover (BTSC) and Minimum Off-Target Set Cover (MOTSC).
• BTSC balances disease gene coverage and minimizes off-target hits.
• MOTSC ensures full disease gene coverage while minimizing off-target effects.

Main Results:

• Both BTSC and MOTSC showed significantly faster running times than exhaustive search with comparable accuracy.
• Algorithms successfully identified known drug combinations and predicted novel ones for real disease gene sets.
• A web-based tool was developed for iterative searching of optimal drug combinations.

Conclusions:

• The developed algorithms provide an efficient and accurate computational approach for drug combination prediction.
• These tools can guide experimental research, reducing costs and accelerating the discovery of effective therapies.
• The freely available web tool facilitates broader application in drug discovery.