title: An exact algorithm for finding cancer driver somatic genome alterations: the weighted mutually exclusive maximum set cover problem.
abstract: BACKGROUND
  The mutual exclusivity of somatic genome alterations (SGAs), such as somatic mutations and copy number alterations, is an important observation of tumors and is widely used to search for cancer signaling pathways or SGAs related to tumor development. However, one problem with current methods that use mutual exclusivity is that they are not signal-based; another problem is that they use heuristic algorithms to handle the NP-hard problems, which cannot guarantee to find the optimal solutions of their models.
  
  
  METHODS
  In this study, we propose a novel signal-based method that utilizes the intrinsic relationship between SGAs on signaling pathways and expression changes of downstream genes regulated by pathways to identify cancer signaling pathways using the mutually exclusive property. We also present a relatively efficient exact algorithm that can guarantee to obtain the optimal solution of the new computational model.
  
  
  RESULTS
  We have applied our new model and exact algorithm to the breast cancer data. The results reveal that our new approach increases the capability of finding better solutions in the application of cancer research. Our new exact algorithm has a time complexity of [Formula: see text](Note: Following the recent convention, we use a star * to represent that the polynomial part of the time complexity is neglected), which has solved the NP-hard problem of our model efficiently.
  
  
  CONCLUSIONS
  Our new method and algorithm can discover the true causes behind the phenotypes, such as what SGA events lead to abnormality of the cell cycle or make the cell metastasis lose control in tumors; thus, it identifies the target candidates for precision (or target) therapeutics.
authors.affiliation: Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15206 USA.
authors.forename: Songjian
authors.initials: S
authors.lastname: Lu
authors.affiliation: Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15206 USA.
authors.forename: Gunasheil
authors.initials: G
authors.lastname: Mandava
authors.affiliation: Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15206 USA.
authors.forename: Gaibo
authors.initials: G
authors.lastname: Yan
authors.affiliation: Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15206 USA.
authors.forename: Xinghua
authors.initials: X
authors.lastname: Lu
keywords: Gene signature; Mutual exclusivity; Somatic genome alteration