Graph theory enables drug repurposing. How a mathematical model can drive the discovery of hidden Mechanisms of Action

Ruggero Gramatica, Tiziana di Matteo, Stefano Giorgetti, Massimo Barbiani, Dorian Bevec, Tomaso AstearXiv 2013 · arXiv

Introduction

The biomedical field is currently experiencing an information explosion, with over 20 million papers indexed in PubMed. However, this vast wealth of knowledge is often fragmented across specialized silos. A critical therapeutic link between a known drug and a disease pathway might exist but remain undiscovered because the relevant data points are scattered across different scientific communities.

To address this challenge of "literature-based scientific discovery," researchers have developed a computational framework that combines Natural Language Processing (NLP) and Graph Theory. This approach treats the entirety of scientific literature as a single, interconnected network, allowing for the automated identification of hidden Mechanisms of Action (MoA) and the repurposing of existing medications for new indications.

Methodology: From Text to Knowledge Graphs

The proposed framework utilizes a two-step process to synthesize fragmented information into a coherent biological model.

1. Semantic Information Retrieval

The researchers processed 3 million PubMed abstracts, decomposing them into individual sentences. Using a curated dictionary of 1,606 biological concepts—including peptides, diseases, and proteins—the system identified instances where two concepts co-occurred within the same sentence. To ensure accuracy, the Lesk algorithm was employed for word-sense disambiguation, distinguishing between different meanings of identical terms based on their context.

2. Graph Construction and Analysis

The extracted co-occurrence data forms the basis of a massive "knowledge graph." In this network, nodes represent biological entities, and edges represent the frequency of their co-occurrence in the literature.

The transition from scientific text to a consolidated knowledge graph.

As shown in the figure above, the process involves mapping terms from raw text (a) into localized subgraphs (b, c). These fragmented views are then merged into a unified graph (d), where redundant mentions of the same concept (e.g., "LAM" or "Lung") are collapsed into single, highly-connected nodes. This consolidation reveals the underlying topology of biological relationships.

Identifying Mechanisms of Action via Random Walks

The core innovation of this framework lies in how it analyzes the graph to find therapeutic connections. Rather than simply looking for the shortest path between a drug and a disease, the system employs a stochastic process known as a "random walk."

A Mechanism of Action is conceptualized as a "chain of reasoning"—for example, a drug binding to a receptor, which then modulates a specific protein involved in a disease pathway. The random walk algorithm calculates the "closeness" of two nodes based on the abundance and redundancy of paths connecting them. This approach mirrors biological reality, where redundant pathways often define the strength and robustness of a physiological effect. By simulating a "walker" moving across the weighted edges of the graph, the system can rank the most plausible MoAs even if no single paper has ever explicitly described the entire chain.

Key Results and Clinical Validation

The utility of this mathematical model has been demonstrated through several significant discoveries:

  • Sarcoidosis and VIP: The model identified Vasoactive Intestinal Peptide (VIP) as a high-probability candidate for treating Sarcoidosis. This prediction was validated in a clinical phase II study, where nebulized VIP showed positive immune-regulatory effects in 20 patients.
  • Imatinib for Creutzfeldt-Jakob Disease (CJD): The system suggested repurposing the cancer drug Imatinib (Gleevec) for CJD. It identified a path through the c-Abl kinase, providing a biological rationale for how the drug might inhibit neuronal apoptosis in this rare neurodegenerative condition.
  • Network Topology: Analysis of the resulting knowledge graph revealed it to be a "small world" network. With an average path length of just 1.95, nearly any two biological concepts in the dictionary are separated by only two "hops," highlighting the immense potential for discovering non-obvious connections.

Conclusion and Future Directions

By applying graph theory to the vast corpus of medical literature, this framework transforms passive text into an active discovery engine. While currently limited by the size of its concept dictionary, future iterations aim to incorporate more granular molecular data and clustering methods to identify multi-target therapies. This automated synthesis of knowledge represents a significant step toward more efficient, data-driven drug development and repurposing.

Summary updated

Abstract

We introduced a methodology to efficiently exploit natural-language expressed biomedical knowledge for repurposing existing drugs towards diseases for which they were not initially intended. Leveraging on developments in Computational Linguistics and Graph Theory, a methodology is defined to build a graph representation of knowledge, which is automatically analysed to discover hidden relations between any drug and any disease: these relations are specific paths among the biomedical entities of the graph, representing possible Modes of Action for any given pharmacological compound. These paths are ranked according to their relevance, exploiting a measure induced by a stochastic process defined on the graph. Here we show, providing real-world examples, how the method successfully retrieves known pathophysiological Mode of Actions and finds new ones by meaningfully selecting and aggregating contributions from known bio-molecular interactions. Applications of this methodology are presented, and prove the efficacy of the method for selecting drugs as treatment options for rare diseases.
BibTeX
@misc{gramatica2013graph,
  author = {Ruggero Gramatica and Tiziana di Matteo and Stefano Giorgetti and Massimo Barbiani and Dorian Bevec and Tomaso Aste},
  title = {{Graph theory enables drug repurposing. How a mathematical model can drive the discovery of hidden Mechanisms of Action}},
  year = {2013},
  eprint = {1306.0924},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.0924},
}
Figure