Quantum and Quantum-inspired Methods forde novoDiscovery of Altered Cancer Pathways
Preprint
- 17 November 2019
- preprint
- Published by Cold Spring Harbor Laboratory in bioRxiv
- p. 845719
Abstract
The combinatorial calculations forde novodiscovery of altered pathways in cancer cohorts involve both coverage (i.e. recurrence) and mutual exclusivity, and solving mutual exclusivity problems is NP-hard for classical computers. Advances in quantum computing systems and our classical, quantum-inspired algorithm GAMA (Graver Aug-mented Multi-seed Algorithm) motivated us to revisit methods for identifying altered pathways. Using different types of quantum and classical algorithms, we report novel formulations of the problem that are tailored to these new computational models. Our formulations require fewer binary variables than available methods, and offer a tuning parameter that allows a trade-off between coverage and exclusivity; varying this parameter returns a variety of solutions. We illustrate our formulations and methods with TCGA mutation data for Acute Myeloid Leukemia (AML). Both the D-Wave quantum annealing solver and the classical GAMA solver returned altered pathways that are known to be important in AML, with different tuning parameter values returning alternative altered pathways. Our reduced-variable algorithm and QUBO problem for-mulations demonstrate how quantum annealing-based binary optimization solvers can be used now in cancer genomics.Keywords
This publication has 22 references indexed in Scilit:
- Genomic and Epigenomic Landscapes of Adult De Novo Acute Myeloid LeukemiaNew England Journal of Medicine, 2013
- Simultaneous Identification of Multiple Driver Pathways in CancerPLOS Computational Biology, 2013
- Efficient methods for identifying mutated driver pathways in cancerBioinformatics, 2012
- Mutual exclusivity analysis identifies oncogenic network modulesGenome Research, 2011
- De novo discovery of mutated driver pathways in cancerGenome Research, 2011
- Quantum annealing with manufactured spinsNature, 2011
- Experimental investigation of an eight-qubit unit cell in a superconducting optimization processorPhysical Review B, 2010
- Minor-embedding in adiabatic quantum computation: I. The parameter setting problemQuantum Information Processing, 2008
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- On the foundations of linear and integer linear programming IMathematical Programming, 1975