HIT'nDRIVE: Multi-driver gene prioritization based on hitting time

Raunak Shrestha, Ermin Hodzic, Jake Yeung, Kendric Wang, Thomas Sauerwald, Phuong Dao, Shawn Anderson, Himisha Beltran, Mark A. Rubin, Colin C. Collins, Gholamreza Haffari, S. Cenk Sahinalp

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    9 Citations (Scopus)


    A key challenge in cancer genomics is the identification and prioritization of genomic aberrations that potentially act as drivers of cancer. In this paper we introduce HIT’nDRIVE, 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 expected minimum number of hops in a random walk originating from any aberrant gene to reach an outlier. HIT’nDRIVE thus aims 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). We apply HIT’nDRIVE to identify aberrant genes that potentially act as drivers in a cancer data set and make phenotype predictions using only the potential drivers - more accurately than alternative approaches
    Original languageEnglish
    Title of host publicationResearch in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings
    EditorsRoded Sharan
    Place of PublicationCham Switzerland
    Pages293 - 306
    Number of pages14
    ISBN (Electronic) 9783319052694
    ISBN (Print)9783319052687
    Publication statusPublished - 2014
    EventInternational Conference on Computational Molecular Biology 2014 - Pittsburgh, United States of America
    Duration: 2 Apr 20145 Apr 2014
    Conference number: 18th
    https://link.springer.com/book/10.1007/978-3-319-05269-4 (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceInternational Conference on Computational Molecular Biology 2014
    Abbreviated titleRECOMB 2014
    Country/TerritoryUnited States of America
    Internet address

    Cite this