Finding Mutated Subnetworks Associated with Survival in Cancer

on YouTube ↗33m

" summary

Proposes an algorithm (NoMAS) that uses color-coding plus a network diffusion on network step to search for connected k-gene subnetworks maximizing a normalized log-rank statistic; proves the max-connected log-rank problem is NP-hard but shows NoMAS recovers a planted 10-gene survival-associated module with probability →1 as sample size grows in simulations. Applies to TCGA (GBM, AML), reports subnetworks significant by permutation p-value while none of their individual genes reach significance, and outperforms greedy and additive-score baselines.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:48Cancer Genomes
3. 1:22Single Gene Test recurrent mutation/mutated gene functional, driver mutations
4. 2:07Mutations and Pathways
5. 2:25Finding Cancer Pathways
6. 3:10Finding Set of Genes Important for Cancer Many recent methods...
7. 4:36Mutations and Survival
8. 5:12Finding Genes Associated with Survival Survival Information
9. 6:43Log-rank Test
10. 9:46Results: TCGA Glioblastoma Multiforme (GBM) TCGA GBM: • 268 samples with SNVs and survival data • 780 genes mutated in 23 samples
11. 10:46Subnetworks Associated with Survival Given a subnetwork
12. 11:38Computational Problem
13. 13:57Color-Coding Alon, Yuster, Zwick. STOC 1994 Looking for subnetwork of size 3
14. 16:53Color-Coding in Bioinformatics
15. 17:12NOMAS (Network of Mutations Associated with Survival)
16. 20:02NOMAS on Simulated Data
17. 22:27NOMAS on Cancer Data TOGA: somatic mutations (SNVs and small indels) + survival data
18. 23:06NOMAS vs Other Approaches GEM
19. 25:08TCGA LAML
20. 25:54Acknowledgements

" related talks

• 01h 02mMarkov Chain Mixing Times and Applications IINayantara Bhatnagar · Counting Complexity and Phase Transitions Boot Camp
• 58mStrong Generalization from Small Brains and No Training DataBruno Olshausen · Unknown Futures of Generalization 2024
• 55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order LogicBenjamin Rossman · Symmetry, Logic, Computation 2016
• 01h 03mDecay of Correlations in Spin SystemsYitong Yin · Counting Complexity and Phase Transitions Boot Camp
• 58mMarkov Chain Mixing Times and Applications IIIIvona Bezáková · Counting Complexity and Phase Transitions Boot Camp
• 55mExploring the Relationship Between Innovation and CatastropheDr. Sanjay Jain · Engineering for Research Symposium 2019
• 23mA New Connection Between Node and Edge Depth Robust GraphsJeremiah Blocki, Mike Cinkoske · ITCS 2021
• 01h 07mWhere the Hard Things AreAndrea Montanari · Counting Complexity and Phase Transitions Boot Camp