Algorithms for Combinatorial Problems Arising in the Analysis of Cancer Mutation Networks

on YouTube ↗35m

" summary

Presents concrete algorithms: NOMAS color-coding adapts color-coding to maximize a non‑additive log‑rank survival score and uses permutations on gene labels to assess significance; it finds an 8‑gene GBM subnetwork (263 TCGA samples) mixing PI3K‑AKT and p53/RB genes that is not significant by single‑gene tests. Also formulates the ILP for connected maximum coverage (K genes cover max patients), compares it to greedy/approximation methods, reports fast ILP solves on TCGA graphs and differing biological hits depending on solver and permutation test.

AI-written summary · about

" chapters (21)

1. 0:00Start
2. 0:26Cancer Genomes
3. 1:05Single Gene Test
4. 1:43Mutations and Pathways
5. 1:54Finding Cancer Pathways
6. 2:50Cancer Mutations and Large Networks: Algorithms
7. 3:59(Local) Topology Matters
8. 4:40Influence Graph
9. 5:19Finding Subnetworks Associated with Survival
10. 6:41Log-rank Test
11. 8:10Computational Problem
12. 8:45NOMAS (Network of Mutations Associated with Survival)
13. 9:41Color-Coding Alon, Yuster, Zwick. STOC 1994
14. 15:40NOMAS and Color Coding
15. 17:13NOMAS vs Other Approaches
16. 19:34Discovering Significant Subnetworks
17. 20:48Combinatorial Model
18. 21:55Connected maximum coverage problem
19. 23:45ILP for maximum connected coverage
20. 24:47Comparison with other methods
21. 26:30Acknowledgements