Document Open Access Logo

Differentially Mutated Subnetworks Discovery

Authors Morteza Chalabi Hajkarim, Eli Upfal, Fabio Vandin

PDF
Thumbnail PDF

File

LIPIcs.WABI.2018.18.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Morteza Chalabi Hajkarim
  • Biotech Research and Innovation Centre, University of Copenhagen, Denmark
Eli Upfal
  • Department of Computer Science, Brown University, Providence, RI, USA
Fabio Vandin
  • Department of Information Engineering, University of Padova, Italy

Funding

This work is supported, in part, by University of Padova project SID2017 and STARS: Algorithms for Inferential Data Mining, and by NSF grant IIS-1247581.
  • Vandin, Fabio: corresponding author

Cite AsGet BibTex

Morteza Chalabi Hajkarim, Eli Upfal, and Fabio Vandin. Differentially Mutated Subnetworks Discovery. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.WABI.2018.18

Abstract

We study the problem of identifying differentially mutated subnetworks of a large gene-gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem and show that the problem is NP-hard. We propose a novel and efficient algorithm, called DAMOKLE to identify differentially mutated subnetworks given genome-wide mutation data for two sets of cancer samples. We prove that DAMOKLE identifies subnetworks with a statistically significant difference in mutation frequency when the data comes from a reasonable generative model, provided enough samples are available. We test DAMOKLE on simulated and real data, showing that DAMOKLE does indeed find subnetworks with significant differences in mutation frequency and that it provides novel insights not obtained by standard methods.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Applied computing → Biological networks
  • Applied computing → Computational genomics
Keywords
  • Cancer genomics
  • network analysis
  • combinatorial algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Rebecca Sarto Basso, Dorit S Hochbaum, and Fabio Vandin. Efficient algorithms to discover alterations with complementary functional association in cancer. arXiv preprint arXiv:1803.09721, 2018. Google Scholar
  2. Michele Ceccarelli, Floris P Barthel, Tathiane M Malta, Thais S Sabedot, Sofie R Salama, Bradley A Murray, Olena Morozova, Yulia Newton, Amie Radenbaugh, Stefano M Pagnotta, et al. Molecular profiling reveals biologically discrete subsets and pathways of progression in diffuse glioma. Cell, 164(3):550-563, 2016. Google Scholar
  3. Fengju Chen, Yiqun Zhang, Edwin Parra, Jaime Rodriguez, Carmen Behrens, Rehan Akbani, Yiling Lu, JM Kurie, Don L Gibbons, Gordon B Mills, et al. Multiplatform-based molecular subtypes of non-small-cell lung cancer. Oncogene, 36(10):1384, 2017. Google Scholar
  4. Ara Cho, Jung Eun Shim, Eiru Kim, Fran Supek, Ben Lehner, and Insuk Lee. Muffinn: cancer gene discovery via network analysis of somatic mutation data. Genome biology, 17(1):129, 2016. Google Scholar
  5. Giovanni Ciriello, Ethan Cerami, Chris Sander, and Nikolaus Schultz. Mutual exclusivity analysis identifies oncogenic network modules. Genome research, 22(2):398-406, 2012. Google Scholar
  6. Giovanni Ciriello, Martin L Miller, Bülent Arman Aksoy, Yasin Senbabaoglu, Nikolaus Schultz, and Chris Sander. Emerging landscape of oncogenic signatures across human cancers. Nature genetics, 45(10):1127, 2013. Google Scholar
  7. Lenore Cowen, Trey Ideker, Benjamin J Raphael, and Roded Sharan. Network propagation: a universal amplifier of genetic associations. Nature Reviews Genetics, 2017. Google Scholar
  8. Phuong Dao, Kendric Wang, Colin Collins, Martin Ester, Anna Lapuk, and S Cenk Sahinalp. Optimally discriminative subnetwork markers predict response to chemotherapy. Bioinformatics, 27(13):i205-i213, 2011. Google Scholar
  9. Jishnu Das and Haiyuan Yu. Hint: High-quality protein interactomes and their applications in understanding human disease. BMC Syst Biol, 6:92, 2012. URL: http://dx.doi.org/10.1186/1752-0509-6-92.
  10. Levi A Garraway and Eric S Lander. Lessons from the cancer genome. Cell, 153(1):17-37, Mar 2013. URL: http://dx.doi.org/10.1016/j.cell.2013.03.002.
  11. Katherine A Hoadley, Christina Yau, Denise M Wolf, Andrew D Cherniack, David Tamborero, Sam Ng, Max DM Leiserson, Beifang Niu, Michael D McLellan, Vladislav Uzunangelov, et al. Multiplatform analysis of 12 cancer types reveals molecular classification within and across tissues of origin. Cell, 158(4):929-944, 2014. Google Scholar
  12. Matan Hofree, John P Shen, Hannah Carter, Andrew Gross, and Trey Ideker. Network-based stratification of tumor mutations. Nat Methods, 10(11):1108-15, Nov 2013. URL: http://dx.doi.org/10.1038/nmeth.2651.
  13. Borislav H Hristov and Mona Singh. Network-based coverage of mutational profiles reveals cancer genes. arXiv preprint arXiv:1704.08544, 2017. Google Scholar
  14. Cyriac Kandoth, Michael D McLellan, Fabio Vandin, Kai Ye, Beifang Niu, Charles Lu, Mingchao Xie, Qunyuan Zhang, Joshua F McMichael, Matthew A Wyczalkowski, Mark D M Leiserson, Christopher A Miller, John S Welch, Matthew J Walter, Michael C Wendl, Timothy J Ley, Richard K Wilson, Benjamin J Raphael, and Li Ding. Mutational landscape and significance across 12 major cancer types. Nature, 502(7471):333-9, Oct 2013. URL: http://dx.doi.org/10.1038/nature12634.
  15. Shinuk Kim, Mark Kon, and Charles DeLisi. Pathway-based classification of cancer subtypes. Biology direct, 7(1):21, 2012. Google Scholar
  16. Yoo-Ah Kim, Dong-Yeon Cho, Phuong Dao, and Teresa M Przytycka. Memcover: integrated analysis of mutual exclusivity and functional network reveals dysregulated pathways across multiple cancer types. Bioinformatics, 31(12):i284-i292, 2015. Google Scholar
  17. Marine Le Morvan, Andrei Zinovyev, and Jean-Philippe Vert. Netnorm: capturing cancer-relevant information in somatic exome mutation data with gene networks for cancer stratification and prognosis. PLoS computational biology, 13(6):e1005573, 2017. Google Scholar
  18. Mark D M Leiserson, Fabio Vandin, Hsin-Ta Wu, Jason R Dobson, Jonathan V Eldridge, Jacob L Thomas, Alexandra Papoutsaki, Younhun Kim, Beifang Niu, Michael McLellan, Michael S Lawrence, Abel Gonzalez-Perez, David Tamborero, Yuwei Cheng, Gregory A Ryslik, Nuria Lopez-Bigas, Gad Getz, Li Ding, and Benjamin J Raphael. Pan-cancer network analysis identifies combinations of rare somatic mutations across pathways and protein complexes. Nat Genet, 47(2):106-14, Feb 2015. URL: http://dx.doi.org/10.1038/ng.3168.
  19. Chao Lu and C David Allis. Swi/snf complex in cancer. Nature genetics, 49(2):178-179, 2017. Google Scholar
  20. Raghvendra Mall, Luigi Cerulo, Halima Bensmail, Antonio Iavarone, and Michele Ceccarelli. Detection of statistically significant network changes in complex biological networks. BMC systems biology, 11(1):32, 2017. Google Scholar
  21. Cancer Genome Atlas Network et al. Comprehensive molecular characterization of human colon and rectal cancer. Nature, 487(7407):330, 2012. Google Scholar
  22. Cancer Genome Atlas Research Network et al. Integrated genomic characterization of oesophageal carcinoma. Nature, 541(7636):169-175, 2017. Google Scholar
  23. Cancer Genome Atlas Research Network et al. Integrated genomic characterization of pancreatic ductal adenocarcinoma. Cancer cell, 32(2):185, 2017. Google Scholar
  24. Sergio Pulido-Tamayo, Bram Weytjens, Dries De Maeyer, and Kathleen Marchal. Ssa-me detection of cancer driver genes using mutual exclusivity by small subnetwork analysis. Scientific reports, 6, 2016. Google Scholar
  25. Srinivas Vinod Saladi, Kenneth Ross, Mihriban Karaayvaz, Purushothama R Tata, Hongmei Mou, Jayaraj Rajagopal, Sridhar Ramaswamy, and Leif W Ellisen. Actl6a is co-amplified with p63 in squamous cell carcinoma to drive yap activation, regenerative proliferation, and poor prognosis. Cancer cell, 31(1):35-49, 2017. Google Scholar
  26. Raunak Shrestha, Ermin Hodzic, Thomas Sauerwald, Phuong Dao, Kendric Wang, Jake Yeung, Shawn Anderson, Fabio Vandin, Gholamreza Haffari, Colin C Collins, et al. Hit'ndrive: patient-specific multidriver gene prioritization for precision oncology. Genome research, 27(9):1573-1588, 2017. Google Scholar
  27. Fenghao Sun, Xiaodong Yang, Yulin Jin, Li Chen, Lin Wang, Mengkun Shi, Cheng Zhan, Yu Shi, and Qun Wang. Bioinformatics analyses of the differences between lung adenocarcinoma and squamous cell carcinoma using the cancer genome atlas expression data. Molecular medicine reports, 16(1):609-616, 2017. Google Scholar
  28. Fabio Vandin. Computational methods for characterizing cancer mutational heterogeneity. Frontiers in genetics, 8:83, 2017. Google Scholar
  29. Fabio Vandin, Eli Upfal, and Benjamin J Raphael. Algorithms for detecting significantly mutated pathways in cancer. Journal of Computational Biology, 18(3):507-522, 2011. Google Scholar
  30. Charles J Vaske, Stephen C Benz, J Zachary Sanborn, Dent Earl, Christopher Szeto, Jingchun Zhu, David Haussler, and Joshua M Stuart. Inference of patient-specific pathway activities from multi-dimensional cancer genomics data using paradigm. Bioinformatics, 26(12):i237-i245, 2010. Google Scholar
  31. Bert Vogelstein and Kenneth W Kinzler. Cancer genes and the pathways they control. Nature medicine, 10(8):789-799, 2004. Google Scholar
  32. Bert Vogelstein, Nickolas Papadopoulos, Victor E Velculescu, Shibin Zhou, Luis A Diaz, Jr, and Kenneth W Kinzler. Cancer genome landscapes. Science, 339(6127):1546-58, Mar 2013. URL: http://dx.doi.org/10.1126/science.1235122.
  33. Michael R Young and David L Craft. Pathway-informed classification system (pics) for cancer analysis using gene expression data. Cancer informatics, 15:CIN-S40088, 2016. Google Scholar
  34. Haiyuan Yu, Leah Tardivo, Stanley Tam, Evan Weiner, Fana Gebreab, Changyu Fan, Nenad Svrzikapa, Tomoko Hirozane-Kishikawa, Edward Rietman, Xinping Yang, Julie Sahalie, Kourosh Salehi-Ashtiani, Tong Hao, Michael E Cusick, David E Hill, Frederick P Roth, Pascal Braun, and Marc Vidal. Next-generation sequencing to generate interactome datasets. Nat Methods, 8(6):478-80, Jun 2011. URL: http://dx.doi.org/10.1038/nmeth.1597.
  35. Ahmet Zehir, Ryma Benayed, Ronak H Shah, Aijazuddin Syed, Sumit Middha, Hyunjae R Kim, Preethi Srinivasan, Jianjiong Gao, Debyani Chakravarty, Sean M Devlin, et al. Mutational landscape of metastatic cancer revealed from prospective clinical sequencing of 10,000 patients. Nature Medicine, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact