Simple Models and Exact Algorithms for Computing Network Modules

on YouTube ↗31m

" summary

Presents a sparse pairwise alignment that restricts each node to a candidate set and encodes edge conservation as a quadratic objective, solved by Lagrangian relaxation and variable splitting; on STRING networks with ~150,000 edges the method (Natalie) reaches near-optimal lower bounds within 1–2% and beats a recent tool (elegua) under a 10-minute CPU limit. Also frames active modules as the maximum-weight connected subgraph, reduces it to prize-collecting Steiner, ships an ILP solver and a Cytoscape plugin, and pinpoints an HGF–MET–HCF axis validated by expression follow-up.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 0:30Network biology
3. 1:45Subnetwork modules
4. 3:35Pairwise restricted global network alignment
5. 5:50Quadratic assignment
6. 7:45Integer programming model
7. 15:20How to model the signal?
8. 19:26Results: Herpesvirus project
9. 23:21Why simple models ? Systems

" related talks

• 01h 06mIntroduction to Biological Network Analysis III: Identifying Network ModulesRoded Sharan · Algorithmic Challenges in Genomics Boot Camp
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 49mIntroduction to Biological Network Analysis IV: Network Alignment and QueryingRoded Sharan · Algorithmic Challenges in Genomics Boot Camp
• 38mThe NetworkL python packageMoreno Bonaventura · PyData London 2016
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IVTamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 55mDistribution-Free Models of Social and Information NetworksTim Roughgarden · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)