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

    6 Citations (Scopus)

    Abstract

    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
    PublisherSpringer
    Pages293 - 306
    Number of pages14
    ISBN (Electronic) 9783319052694
    ISBN (Print)9783319052687
    DOIs
    Publication statusPublished - 2014
    EventInternational Conference on Computational Molecular Biology 2014 - Pittsburgh, United States of America
    Duration: 2 Apr 20145 Apr 2014
    Conference number: 18th
    http://murphylab.web.cmu.edu/compbio/recomb/

    Publication series

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

    Conference

    ConferenceInternational Conference on Computational Molecular Biology 2014
    Abbreviated titleRECOMB 2014
    CountryUnited States of America
    CityPittsburgh
    Period2/04/145/04/14
    Internet address

    Cite this

    Shrestha, R., Hodzic, E., Yeung, J., Wang, K., Sauerwald, T., Dao, P., ... Sahinalp, S. C. (2014). HIT'nDRIVE: Multi-driver gene prioritization based on hitting time. In R. Sharan (Ed.), Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings (pp. 293 - 306). (Lecture Notes in Computer Science; Vol. 8394). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-05269-4_23
    Shrestha, Raunak ; Hodzic, Ermin ; Yeung, Jake ; Wang, Kendric ; Sauerwald, Thomas ; Dao, Phuong ; Anderson, Shawn ; Beltran, Himisha ; Rubin, Mark A. ; Collins, Colin C. ; Haffari, Gholamreza ; Sahinalp, S. Cenk. / HIT'nDRIVE: Multi-driver gene prioritization based on hitting time. Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings. editor / Roded Sharan. Cham Switzerland : Springer, 2014. pp. 293 - 306 (Lecture Notes in Computer Science).
    @inproceedings{e9aba16b45bb450a86b740418259df21,
    title = "HIT'nDRIVE: Multi-driver gene prioritization based on hitting time",
    abstract = "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",
    author = "Raunak Shrestha and Ermin Hodzic and Jake Yeung and Kendric Wang and Thomas Sauerwald and Phuong Dao and Shawn Anderson and Himisha Beltran and Rubin, {Mark A.} and Collins, {Colin C.} and Gholamreza Haffari and Sahinalp, {S. Cenk}",
    year = "2014",
    doi = "10.1007/978-3-319-05269-4_23",
    language = "English",
    isbn = "9783319052687",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "293 -- 306",
    editor = "Roded Sharan",
    booktitle = "Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings",

    }

    Shrestha, R, Hodzic, E, Yeung, J, Wang, K, Sauerwald, T, Dao, P, Anderson, S, Beltran, H, Rubin, MA, Collins, CC, Haffari, G & Sahinalp, SC 2014, HIT'nDRIVE: Multi-driver gene prioritization based on hitting time. in R Sharan (ed.), Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings. Lecture Notes in Computer Science, vol. 8394, Springer, Cham Switzerland, pp. 293 - 306, International Conference on Computational Molecular Biology 2014, Pittsburgh, United States of America, 2/04/14. https://doi.org/10.1007/978-3-319-05269-4_23

    HIT'nDRIVE: Multi-driver gene prioritization based on hitting time. / Shrestha, Raunak; Hodzic, Ermin; Yeung, Jake; Wang, Kendric; Sauerwald, Thomas; Dao, Phuong; Anderson, Shawn; Beltran, Himisha; Rubin, Mark A.; Collins, Colin C.; Haffari, Gholamreza; Sahinalp, S. Cenk.

    Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings. ed. / Roded Sharan. Cham Switzerland : Springer, 2014. p. 293 - 306 (Lecture Notes in Computer Science; Vol. 8394).

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

    TY - GEN

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

    AU - Shrestha, Raunak

    AU - Hodzic, Ermin

    AU - Yeung, Jake

    AU - Wang, Kendric

    AU - Sauerwald, Thomas

    AU - Dao, Phuong

    AU - Anderson, Shawn

    AU - Beltran, Himisha

    AU - Rubin, Mark A.

    AU - Collins, Colin C.

    AU - Haffari, Gholamreza

    AU - Sahinalp, S. Cenk

    PY - 2014

    Y1 - 2014

    N2 - 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

    AB - 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

    UR - http://goo.gl/l2opDk

    U2 - 10.1007/978-3-319-05269-4_23

    DO - 10.1007/978-3-319-05269-4_23

    M3 - Conference Paper

    SN - 9783319052687

    T3 - Lecture Notes in Computer Science

    SP - 293

    EP - 306

    BT - Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings

    A2 - Sharan, Roded

    PB - Springer

    CY - Cham Switzerland

    ER -

    Shrestha R, Hodzic E, Yeung J, Wang K, Sauerwald T, Dao P et al. HIT'nDRIVE: Multi-driver gene prioritization based on hitting time. In Sharan R, editor, Research in Computational Molecular Biology: 18th Annual International Conference (RECOMB 2014): Proceedings. Cham Switzerland: Springer. 2014. p. 293 - 306. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-05269-4_23