Predicting combinations of drugs by exploiting graph embedding of heterogeneous networks

Fei Song, Shiyin Tan, Zengfa Dou, Xiaogang Liu, Xiaoke Ma

TL;DR

This paper introduces SeHNE, a novel algorithm that predicts effective drug combinations by leveraging graph embeddings of complex, heterogeneous biological networks. By jointly learning drug features and predicting combinations, SeHNE significantly improves accuracy over existing methods, offering a more efficient path to discovering synergistic drug therapies.

What Problem Does This Paper Address?

Identifying effective drug combinations is crucial for treating complex diseases like cancer, as combinations can enhance efficacy and reduce toxicity. However, predicting these combinations is challenging due to the intricate interactions involved. Traditional methods often treat feature selection and prediction as independent steps, leading to suboptimal performance. Furthermore, existing computational approaches frequently overlook the rich, indirect relationships within biological systems, limiting their predictive power. This paper aims to bridge this gap by developing a unified framework that effectively models and exploits these complex relationships for more accurate drug combination prediction.

Methods

The core of this work is the SeHNE (Semi-supervised Heterogeneous Network Embedding) algorithm. It constructs a heterogeneous network by integrating three key types of biological data:

  • Drug-drug similarity: Based on Anatomical Therapeutic Chemical (ATC) coding and chemical structure similarity.
  • Drug-target interactions: Linking drugs to their protein targets.
  • Protein-protein interactions (PPI): Capturing how proteins interact with each other.

SeHNE then employs graph embedding techniques, specifically Non-negative Matrix Factorization (NMF) and Laplacian regularization, to learn low-dimensional feature representations (embeddings) for drugs. A key innovation is joint learning, where feature extraction (graph embedding) and drug combination prediction (using a Support Vector Machine - SVM) are performed simultaneously. This allows the feature extraction process to be guided by the prediction task, leading to more discriminative features. The algorithm iteratively updates drug embeddings, drug-target embeddings, and the prediction model until convergence.

Datasets

The study utilizes several publicly available datasets:

  • DrugCombDB: For drug combination data, specifically from leukemia-related cell lines.
  • DrugBank, KEGG, and Therapeutic Target Database (TTD): For drug-target interactions.
  • Human PPI network data: For protein-protein interactions.

The authors report obtaining a dataset of 370 drugs and 18,126 drug-drug combinations, comprising 5903 synergistic and 12,223 antagonistic combinations.

Key Insights and Ideas

  • The Power of Joint Learning: The most significant insight is that jointly learning drug features and predicting combinations leads to superior performance compared to independent learning. This suggests that the prediction task can effectively guide the feature extraction process, making the learned features more relevant and discriminative.
  • Heterogeneous Networks are Key: Integrating diverse biological data (drug similarity, drug-target, PPI) into a single heterogeneous network captures a more comprehensive picture of drug interactions than using isolated data sources.
  • Indirect Relations Matter: Graph embedding effectively captures the subtle, indirect relationships within the network, which are often missed by traditional methods that focus on direct feature comparisons.
  • Robustness to Input: The study demonstrates that SeHNE is relatively insensitive to the choice of similarity measure (ATC vs. chemical structure) and the specific classifier used (SVM, KNN, LDA, etc.), highlighting its generalizability.

Key Results

  • SeHNE significantly outperforms state-of-the-art methods in predicting drug combinations, achieving higher AUC (Area Under the Curve) and AP (Average Precision) scores. For instance, the paper shows SeHNE achieving an accuracy of 0.7553 on test data in an illustrative example.
  • The joint learning strategy consistently outperformed independent learning across various metrics.
  • The algorithm demonstrates efficient convergence, typically reaching optimal performance within 30 iterations.
  • SeHNE is shown to be robust to the choice of classifier and similarity metrics.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Focus on Drug Pairs: The current algorithm only predicts combinations of two drugs. Extending this to higher-order combinations (three or more drugs) is a significant challenge due to the exponentially increasing search space. Future work should focus on strategies to narrow down the candidate space for high-order combinations.
  • Ignoring Intrinsic Drug Features: SeHNE primarily relies on the topological structure of heterogeneous networks to extract drug features. Future research could explore integrating intrinsic drug attributes, such as molecular structure and function, to further enhance prediction accuracy.
  • Limited Information Integration: The current model integrates drug and protein information but does not consider other crucial biological factors like gene expression, drug responses, or the immune micro-environment, which could be valuable for a more holistic understanding of drug combinations.

Summary updated

Abstract

Drug combination, offering an insight into the increased therapeutic efficacy and reduced toxicity, plays an essential role in the therapy of many complex diseases. Although significant efforts have been devoted to the identification of drugs, the identification of drug combination is still a challenge. The current algorithms assume that the independence of feature selection and drug prediction procedures, which may result in an undesirable performance. To address this issue, we develop a novel Semi-supervised Heterogeneous Network Embedding algorithm (called SeHNE) to predict the combination patterns of drugs by exploiting the graph embedding. Specifically, the ATC similarity of drugs, drug–target, and protein–protein interaction networks are integrated to construct the heterogeneous networks. Then, SeHNE jointly learns drug features by exploiting the topological structure of heterogeneous networks and predicting drug combination. One distinct advantage of SeHNE is that features of drugs are extracted under the guidance of classification, which improves the quality of features, thereby enhancing the performance of prediction of drugs. Experimental results demonstrate that the proposed algorithm is more accurate than state-of-the-art methods on various data, implying that the joint learning is promising for the identification of drug combination. The proposed model and algorithm provide an effective strategy for the prediction of combinatorial patterns of drugs, implying that the graph-based drug prediction is promising for the discovery of drugs.
BibTeX
@article{song2022predicting,
  author = {Fei Song and Shiyin Tan and Zengfa Dou and Xiaogang Liu and Xiaoke Ma},
  title = {{Predicting combinations of drugs by exploiting graph embedding of heterogeneous networks}},
  journal = {BMC Bioinformatics},
  year = {2022},
  url = {https://openreview.net/forum?id=IAC9VbYsqp},
}
Figure