Use of ILP for cancer driver prioritization

Project ID
FG-408
Project Categories
Computer Science
Project Keywords
Completed
Abstract
A key challenge in cancer genomics is the identification and prioritization of genomic aberrations that potentially act as drivers of cancer. We introduce a combinatorial method to identify aberrant genes that can collectively influence possibly distant "outlier" genes based on what we call the "random-walk facility location" (RWFL) problem on an interaction network. RWFL differs from the standard facility location problem by its use of "multi-hitting time", the minimum expected number of hops in a random walk originating from any aberrant gene to reach an outlier. WE thus aim to find the smallest set of aberrant genes from which one can reach outliers within a desired multi-hitting time. For that it estimates multi-hitting time based on the independent hitting times from the drivers to any given outlier and reduces the RWFL to a weighted multi-set cover problem, which it solves as an integer linear program (ILP).
Use of FutureSystems
Running cplex / gurobi in order to solve ILP problems that give solution to multi-hitting time approximations.
Scale of Use
Will be running cplex/gurobi programs on datasets. Each run might take more than a day to solve.