A novel and efficient algorithm for de novo discovery of mutated driver pathways in cancer

Binghui Liu, Chong Wu, Xiaotong T Shen, Wei Pan

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Next-generation sequencing studies on cancer somatic mutations have discovered that driver mutations tend to appear in most tumor samples, but they barely overlap in any single tumor sample, presumably because a single driver mutation can perturb the whole pathway. Based on the corresponding new concepts of coverage and mutual exclusivity, new methods can be designed for de novo discovery of mutated driver pathways in cancer. Since the computational problem is a combinatorial optimization with an objective function involving a discontinuous indicator function in high dimension, many existing optimization algorithms, such as a brute force enumeration, gradient descent and Newton’s methods, are practically infeasible or directly inapplicable. We develop a new algorithm based on a novel formulation of the problem as nonconvex programming and nonconvex regularization. The method is computationally more efficient, effective and scalable than existing Monte Carlo searching and several other algorithms, which have been applied to The Cancer Genome Atlas (TCGA) project. We also extend the new method for integrative analysis of both mutation and gene expression data. We demonstrate the promising performance of the new methods with applications to three cancer datasets to discover de novo mutated driver pathways.

Original languageEnglish (US)
Pages (from-to)1481-1512
Number of pages32
JournalAnnals of Applied Statistics
Issue number3
StatePublished - Sep 2017

Bibliographical note

Funding Information:
Received September 2015; revised March 2017. 1Supported in part by the Minnesota Supercomputing Institute (MSI) and NIH Grants R01GM113250, R01HL105397 and R01HL116720, by NSF Grants DMS-09-06616 and DMS-12-07771 and by NSFC Grant 11571068. 2Supported by a University of Minnesota Dissertation Fellowship. Key words and phrases. DNA sequencing, driver mutations, optimization, subset selection, truncated L1 penalty.

Publisher Copyright:
© Institute of Mathematical Statistics, 2017.


  • DNA sequencing
  • Driver mutations
  • Optimization
  • Subset selection
  • Truncated L penalty


Dive into the research topics of 'A novel and efficient algorithm for de novo discovery of mutated driver pathways in cancer'. Together they form a unique fingerprint.

Cite this