Abstract
Many research questions can be approached by extracting meaningful subnetwork modules from biological networks. Some approaches for this task are based on network information alone, e.g., to identify protein complexes or conserved subnetworks, while others compute modules based on additional information such as gene expression profiles or other “omics” data.
I will present simple combinatorial models for two different problems: global network alignment and active module discovery. Despite their simplicity, the models lead to NP-hard optimization problems. I will present exact algorithms that build on previous work of the mathematical optimization community on the related problems of Quadratic Assignment and Prize-Collecting Steiner Trees. The resulting algorithms work well in practice, both on simulated and real-world data from various case studies. If time permits, I will describe our recent efforts to address the combined problem of finding conserved active modules.