This program is the implementation component of the paper "Mapping Cancer Metastasis Pathways Using Probability-Weighted Depth-First Search on a Human Organ Graph", IF2211 Algorithm Strategy, Semester II 2025/2026, Institut Teknologi Bandung.
weighted-dfs-cancer-metastasis-pathway-mapping/
├── src/
│ ├── main.py — entry point, runs the program interactively
│ ├── graph_constructor.py — builds the directed weighted graph from CSV
│ ├── dfs_engine.py — modified DFS with probability propagation
│ │ and threshold-based pruning
│ ├── result_analyzer.py — ranks pathways, computes coverage and stats
│ ├── visualizer.py — generates the combined 3-panel output figure
│ ├── extract_metmap_data.py — extracts edge weights from the raw MetMap
│ │ Excel file and writes data_metastasis.csv
│ └── data_metastasis.csv — graph input: 76 directed edges derived from
│ MetMap (16 primary lineages × 5 target organs)
└── output/ — generated automatically on first run, one .png file is saved here per run
The MetMap source file (Supplementary_Table_04_MetMap_500_met_potential.xlsx)
is not included in this repository. See the Data section below for how to
obtain it and regenerate data_metastasis.csv.
Python 3.8 or later. Install dependencies with:
pip install networkx matplotlib pandas openpyxlRun from inside the src/ folder:
cd src
python main.pyThe program runs interactively and asks for two inputs.
1. Primary organ — the organ where cancer originates. A list of all 17 available organs is printed before the prompt:
Organ list : bone
brain
breast
central_nervous_system
colon
endometrium
esophagus
kidney
liver
lung
melanoma
ovary
pancreas
prostate
stomach
thyroid
urinary_tract
Enter the primary organ where the cancer started:
2. Theta (θ) — the pruning threshold. A pathway is discarded the moment its cumulative probability drops below this value. Because every edge weight is strictly less than 1, cumulative probability always decreases at each step, so theta alone guarantees that the algorithm terminates without separate depth limit.
Theta is the pruning threshold
Typical useful range is 0.001 (inclusive, many long low-probability paths)
to 0.05 (strict, only short/likely paths survive),
recommended default is 0.01.
Enter theta:
=== All 17 Pathways Above Threshold ===
rank route probability length
1 breast -> lung 0.158400 1
2 breast -> liver 0.146000 1
3 breast -> bone 0.090100 1
4 breast -> kidney 0.084000 1
5 breast -> brain 0.053200 1
6 breast -> lung -> liver 0.037752 2
...
=== Coverage ===
Organs reached : 6/17 (35.29%)
Organ list : bone, brain, breast, kidney, liver, lung
=== Summary Statistics ===
n_paths : 17
avg_probability : 0.0447
max_probability : 0.1584
min_probability : 0.0101
avg_path_length : 1.71
max_path_length : 2
=== Organ Frequency Across All Pathways ===
organ frequency
lung 8
liver 7
bone 6
kidney 5
brain 3
A combined 3-panel figure is saved automatically to the output/ folder
with a filename that encodes the run parameters:
output/YYYYMMDD_HHMMSS.png
For example: output\20260619_075955.png
The timestamp ensures each run produces a distinct file, so different parameter combinations can be compared without overwriting previous results.
The figure contains three panels side by side:
| Panel | Content |
|---|---|
| Left | Full organ metastasis graph. All 17 nodes in alphabetical circular layout. Edge thickness reflects probability. Primary organ highlighted in yellow. |
| Center | Same graph with every pathway above θ highlighted in a distinct color per pathway. Legend lists pathways by rank. |
| Right | Bar chart of organ appearance frequency across all discovered pathways. |
The file already included in src/ was generated from the official MetMap
supplementary table using extract_metmap_data.py. It contains 76 directed
edges representing average metastasis penetrance from 16 primary cancer
lineages to 5 MetMap target organs (brain, lung, liver, bone, kidney).
Probabilities are the mean penetrance value across all cell lines within each lineage, where penetrance is the fraction of mice in the experimental cohort that developed metastasis to a given organ.
| Lineage | Cell lines | Lineage | Cell lines |
|---|---|---|---|
| lung | 98 | ||
| melanoma | 40 | ||
| central_nervous_system | 35 | ||
| pancreas | 33 | ||
| ovary | 32 | ||
| colon | 27 | ||
| breast | 23 | ||
| esophagus | 23 | ||
| urinary_tract | 23 | ||
| endometrium | 21 | ||
| liver | 17 | ||
| stomach | 17 | ||
| kidney | 16 | ||
| bone | 13 | ||
| thyroid | 10 | ||
| prostate | 4 |
To rebuild the CSV from the raw MetMap file:
- Download
Supplementary_Table_04_MetMap_500_met_potential.xlsxfrom the MetMap supplementary materials (Jin et al., 2020, Nature). - Place it in the
src/folder. - Run:
cd src
python extract_metmap_data.pyThe modified DFS starts from the selected primary organ and recursively visits every reachable successor organ. Two mechanisms extend the standard DFS:
Probability propagation. At every step, the path probability is updated by multiplying the current edge weight with the cumulative probability accumulated so far. A path consisting of k edges e₁, e₂, …, eₖ has cumulative probability P = ∏ w(eᵢ).
Threshold-based pruning. If the cumulative probability of the currently active path falls below θ, that branch is immediately abandoned. Since all edge weights are less than 1, cumulative probability strictly decreases at every step and is guaranteed to eventually fall below any positive θ without needing an explicit depth cap.
Cycle prevention. A visited set local to each active path prevents the same organ from being revisited within a single path. This allows the same organ to appear on a different independent path while still preventing infinite loops within a single traversal.
Every path whose cumulative probability remains at or above θ upon reaching a new organ is stored as a result. The final output is the full set of such paths, sorted by probability.
Jin, X. et al. "A metastasis map of human cancer cell lines." Nature 588, 331–336 (2020). https://doi.org/10.1038/s41586-020-2969-2