Complex Networks and the Drug Repositioning Problem

This Master's thesis analyzes the graph properties and discovery patterns of a multi-level drug-protein network to develop a network diffusion recommendation system for prioritizing drug repurposing candidates against Neglected Tropical Diseases.

The Gist

The Big Picture: The "Drug Detective" Problem

Imagine you are a detective trying to find a cure for a rare, neglected disease (like Malaria or Chagas disease). You have a massive library of existing drugs—thousands of them—that were already invented to treat common things like high blood pressure, cancer, or depression.

The problem? Making a new drug from scratch is like building a house from scratch: it takes 15 years and costs a trillion dollars. It's too slow and too expensive for diseases that don't make much money.

The Solution: Instead of building a new house, why not find an existing house that already has the right rooms and just move it to a new neighborhood? This is called Drug Repositioning. You take an old, safe drug and see if it can treat a new disease.

This thesis is about building a giant, super-smart map (a Network) to help us find these "perfect matches" between old drugs and new diseases much faster.

---

The Map: A Three-Layer City

The author built a digital city with three distinct layers, all connected to each other:

1. The Drug Layer (The Shelves): This is a giant warehouse of medicines. Some drugs are "cousins" because they look chemically similar (like two different brands of aspirin).
2. The Protein Layer (The Locks): Inside our bodies, diseases are often caused by broken "locks" (proteins). Drugs work by finding the right key to lock or unlock them.
3. The Annotation Layer (The ID Cards): Every protein has an ID card. It tells us what family it belongs to (like "Kinase Family"), what job it does, and what other species (like mice or yeast) have similar proteins.

The Magic Connection: The genius of this map is that it connects all three. If Drug A works on Protein X, and Protein X is similar to Protein Y (which causes a neglected disease), then maybe Drug A can treat that disease too.

---

The Tools: How the Detective Works

The author used several clever tricks to navigate this map:

1. The "Group Hug" (Clustering)

Imagine you have 15 million drugs. That's too many to look at one by one. The author grouped them into "families" based on how similar they look.

• The Tanimoto Group: Drugs that share the same chemical "ingredients" (like a cake and a muffin both having flour and eggs).
• The Substructure Group: Drugs where one is literally a smaller piece of the other (like a Lego brick being part of a bigger castle).
• The Analogy: Instead of checking every single person in a city, the detective groups them by neighborhood. If one person in a neighborhood is a doctor, maybe the whole neighborhood has medical knowledge.

2. The "Voting System" (Prioritization)

How do we guess which drug will work on a new disease? The author used a Voting Scheme.

• The Analogy: Imagine you want to find the best restaurant in town, but you've never been there. You ask your friends (the network).
  • If your friend Alice (a known drug) loves Italian food, and she is friends with Bob (a protein), and Bob is friends with Charlie (a new protein causing a disease), the system gives Charlie a "vote" for Italian food.
  • The more votes a drug gets from the network, the more likely it is to be a good cure.

3. The "Time Machine" (Temporal Analysis)

The author looked at when drugs were discovered.

• The "Crawlers" vs. The "Hoppers":
  • Hoppers: These are wild discoveries. A scientist finds a drug that works on a totally new target they've never seen before. (Rare).
  • Crawlers: These are the common discoveries. A scientist takes a drug that works on a human protein and realizes, "Hey, this bug also has a similar protein! Let's try it."
• The Finding: Most drug discoveries are "Crawlers." They don't jump to the unknown; they slowly creep along the path of what we already know. This proves that the "Voting System" works because the real world already does this naturally!

---

The Results: Who Wins the Game?

The author tested this system on five different species: Humans, Mice, Yeast, and two disease-causing parasites (Malaria and Chagas).

• The Surprise: The system worked amazingly well for the parasites (the neglected diseases) but was a bit shaky for Humans and Yeast.
• Why?
  • The Parasites: They are on the "edge" of the map. They are connected to the well-studied Human/Mouse proteins. Because the system knows so much about Humans, it can easily "transfer" that knowledge to the parasites. It's like using a map of New York to navigate a small town nearby; the big landmarks help you find the small streets.
  • Humans/Yeast: They are so central and complex that the "votes" get diluted. Also, we already know almost everything about them, so there's less "new" information to discover.

The "Aha!" Moment

The thesis concludes that similarity is the key.

• If two drugs look alike, they probably hit the same targets.
• If two proteins share the same "ID cards" (domains), they probably react to the same drugs.
• By mapping these connections, we can predict new cures without doing expensive lab experiments first.

The Takeaway

This paper is a blueprint for a Digital Drug Finder. It shows us that by treating biology like a giant social network, we can use the connections between old drugs, proteins, and diseases to solve the hardest medical problems (like neglected tropical diseases) quickly and cheaply.

Instead of reinventing the wheel, we just need to look at the map and see where the wheels are already rolling.

Technical Summary

1. Problem Statement

The thesis addresses the high cost, long timeline (12–15 years), and high failure rate of traditional drug discovery. It focuses on Drug Repositioning (identifying new therapeutic uses for existing drugs), particularly for Neglected Tropical Diseases (NTDs) like Malaria and Chagas disease, where commercial incentives are low.

The core scientific challenge is to leverage chemogenomic data (relationships between drugs, proteins, and biological annotations) to predict novel drug-target interactions. The author posits that complex network theory can reveal non-trivial patterns in this data, allowing for the prioritization of protein targets and the prediction of new drug activities based on structural similarities and shared biological functions.

2. Methodology

The research utilizes a Multilayer Network approach based on data from the TDR Targets database. The methodology is structured as follows:

A. Network Construction

The network is composed of three primary layers:

1. Drug Layer: Nodes represent chemical compounds. Edges represent two types of structural similarity:
   • Tanimoto Similarity: Based on molecular fingerprints (Jaccard index > 0.8).
   • Substructure: Directed relationships where one molecule is a structural subset of another.
2. Protein (Target) Layer: Nodes represent proteins. Edges represent experimentally reported bioactivity (drug-protein interactions).
3. Annotation Layer: Nodes represent functional/structural characteristics of proteins:
   • PFAM Domains: Structural protein subunits.
   • Orthologous Groups: Evolutionary relationships across species.
   • Metabolic Pathways: Biochemical reaction chains.

B. Network Reduction and Clustering

To manage computational complexity and noise, the author identifies Identity Clusters:

• S-clusters: Strongly connected components based on substructure relationships.
• T-clusters: Cliques based on Tanimoto similarity = 1.
  These clusters reduce the network size significantly (approx. 10% node reduction, 47% edge reduction for Tanimoto) while preserving topological information.

C. Projection and Statistical Validation

The bipartite Drug-Protein and Protein-Annotation networks are projected onto single-layer networks to analyze connectivity:

• Projection Methods: Trivial projection (common neighbors), ProbS (diffusion probability), and Statistical Validation (StatVal).
• StatVal: Links are only retained if the number of shared proteins between two annotations is statistically significant (p-value < threshold) compared to a random null model, filtering out spurious correlations.

D. Prioritization Algorithm

A Voting Scheme (VS) (equivalent to K-Nearest Neighbors with K=1) is used for link prediction:

• Goal: Predict the "druggability" of untested proteins.
• Mechanism: Known drug targets act as "seeds." Information (druggability scores) propagates through the network based on protein-protein similarity (induced by shared annotations) to score untested proteins.
• Evaluation: Performance is measured using ROC curves and the AUC-0.1 metric (Area Under Curve for the top 10% of predictions), validated via cross-species leave-one-out testing.

3. Key Contributions

A. Characterization of Chemical Similarity

• Persistence Analysis: The study quantifies the overlap between Tanimoto and Substructure clusters. It finds that Substructure clusters are "stronger" (higher persistence) than Tanimoto clusters. Substructure identity implies a higher probability of sharing protein targets than Tanimoto identity alone.
• Calibration: A calibration curve was established between Tanimoto and Substructure similarity scores, showing that for the same similarity value, substructure implies a higher coincidence of shared targets.

B. Annotation Relevance and Entropy

• Rscore (Relevance Score): A statistical metric (based on Fisher's exact test p-values) was developed to rank annotations by their ability to predict druggability. Kinases, GPCRs, and ion channels were identified as highly relevant.
• Entropy Analysis: The author introduced normalized entropy to measure how well an annotation transfers information between species.
  • Finding: There is a trade-off. Annotations with high relevance (low p-value) often have low entropy (species-specific), while high-entropy annotations (universal) have lower relevance.
  • Key Insight: Specific domains (e.g., DHFR_1, Ribonuc_red) were identified that possess both high relevance and high inter-species entropy, making them ideal bridges for transferring drug knowledge from model organisms to NTD pathogens.

C. Network Topology and Drug Repositioning

• Crawling vs. Hopping: Temporal analysis of the network growth revealed that new drug-target links predominantly arise via "Crawling" (adding links to existing targets or using existing drugs on new targets) rather than "Hopping" (completely novel drug-target pairs). This validates the strategy of repositioning existing drugs.
• Cross-Species Flow: The study demonstrated that pathogenic species (e.g., Trypanosoma cruzi, Plasmodium falciparum) are "easier" to prioritize than model organisms (Human, Yeast) because their druggable proteins are more highly connected to the "core" of model organisms in the network.

4. Key Results

• Prioritization Performance:
  • The voting scheme achieved high AUC-0.1 scores for pathogenic species:
    • Trypanosoma cruzi: 0.851
    • Plasmodium falciparum: 0.705
  • Performance was lower for Homo sapiens (0.641) and Saccharomyces cerevisiae (0.495), attributed to the fact that human/yeast targets are often "peripheral" in the network and less connected to the diverse pool of model organism data.
• Domain Architecture Prediction:
  • By analyzing 4-cliques (tightly connected groups of 4 PFAM domains) in the projected annotation network, the author successfully prioritized drugs with specific mechanisms of action (e.g., kinase inhibitors, vasodilators).
  • The method successfully identified a drug (D 173221) for a protein with a specific domain architecture that was not previously in the database, validating the predictive power of the network projection.
• Temporal Evolution:
  • 80% of "unique targets" (targets with only one known drug) are reached by drugs that also target other proteins, reinforcing the polypharmacology nature of drug discovery.
  • The network growth is dominated by "crawling," confirming that new discoveries are largely extensions of existing knowledge rather than random discoveries.

5. Significance and Conclusion

This thesis provides a robust computational framework for drug repositioning specifically tailored for neglected diseases. Its significance lies in:

1. Data Integration: It successfully integrates chemical, genomic, and functional data into a unified multilayer network, demonstrating that structural similarity in drugs correlates strongly with functional similarity in proteins.
2. Methodological Innovation: The use of Statistical Validation (StatVal) for projecting bipartite networks filters noise effectively, revealing only biologically significant associations.
3. Strategic Insight: The identification of "high-entropy, high-relevance" annotations provides a concrete strategy for transferring drug knowledge from well-studied model organisms to neglected pathogens.
4. Validation: The high success rate in prioritizing targets for T. cruzi and P. falciparum validates the hypothesis that network-based "crawling" is an effective mechanism for identifying new therapeutic targets in under-researched areas.

The work concludes that complex network analysis is not just a theoretical exercise but a practical tool that can significantly reduce the cost and risk of drug development for neglected tropical diseases by leveraging existing chemogenomic data.