Top

Published in:

29-01-2018 | Methodologies and Application

Biclustering with a quantum annealer

Authors: Lorenzo Bottarelli, Manuele Bicego, Matteo Denitto, Alessandra Di Pierro, Alessandro Farinelli, Riccardo Mengoni

Published in: Soft Computing | Issue 18/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Several problem in Artificial Intelligence and Pattern Recognition are computationally intractable due to their inherent complexity and the exponential size of the solution space. One example of such problems is biclustering, a specific clustering problem where rows and columns of a data-matrix must be clustered simultaneously. Quantum information processing could provide a viable alternative to combat such a complexity. A notable work in this direction is the recent development of the D-Wave computer, whose processor has been designed to the purpose of solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In this paper, we investigate the use of quantum annealing by providing the first QUBO model for biclustering and a theoretical analysis of its properties (correctness and complexity). We empirically evaluated the accuracy of the model on a synthetic data-set and then performed experiments on a D-Wave machine discussing its practical applicability and embedding properties.

previous article Self-adaptive type-1/type-2 hybrid fuzzy reasoning techniques for two-factored stock index time-series prediction

next article Optimization of thermal parameters in a double pipe heat exchanger with a twisted tape using response surface methodology

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

According to the quantum adiabatic theorem, a quantum system that begins in the non-degenerate ground state of a time-dependent Hamiltonian will remain in the instantaneous ground state provided the Hamiltonian changes sufficiently slowly.

Available at http://www.tik.ee.ethz.ch/sop/bimax (Scenario I—Noise).

Note that only 1097 of 1152 qubits are operational.

An Ising model is frustrated when the competition between ferromagnetic and anti-ferromagnetic couplings leads to a ground state where the interaction energies between spins cannot be simultaneously minimized.

Note that parameter G can always be chosen close to B.

Ayadi W, Elloumi M, Hao J (2012) BiMine+: an efficient algorithm for discovering relevant biclusters of DNA microarray data. Knowl Based Syst 35:224–234CrossRef

Badea L (2009) Generalized clustergrams for overlapping biclusters. In: Proceedings of the 21st international joint conference on artificial intelligence. IJCAI’09. Morgan Kaufmann Publishers Inc., San Francisco, pp 1383–1388

Ben-Dor A, Chor B, Karp R, Yakhini Z (2003) Discovering local structure in gene expression data: the order-preserving submatrix problem. J Comput Biol 10(3–4):373–384CrossRef

Bian Z, Chudak F, Macready WG, Rose G (2010) The Ising model: teaching an old problem new tricks. http://www.dwavesys.com/sites/default/files/weightedmaxsat_v2.pdf

Bian Z, Chudak F, Israel R, Lackey B, Macready WG, Roy A (2014) Discrete optimization using quantum annealing on sparse Ising models. Front Phys 2:56CrossRef

Bicego M, Lovato P, Ferrarini A, Delledonne M (2010) Biclustering of expression microarray data with topic models. In: International conference on pattern recognition (ICPR2010), pp 2728–2731

Boothby T, King AD, Roy A (2016) Fast clique minor generation in chimera qubit connectivity graphs. Quantum Inf Process 15(1):495–508MathSciNetCrossRefMATH

Cai J, Macready WG, Roy A (2014) A practical heuristic for finding graph minors. ArXiv e-prints arXiv:1406.2741

Cheng Y, Church G (2000) Biclustering of expression data. In: Proceedings eighth international conference on intelligent systems for molecular biology (ISMB00), pp 93–103

Dahl ED (2013) Programming with D-Wave: map coloring problem. http://www.dwavesys.com/sites/default/files/MapColoringWP2.pdf

Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H (2016) What is the computational value of finite-range tunneling? Phys Rev X 6(3):031015

Denitto M, Farinelli A, Franco G, Bicego M (2014) A binary factor graph model for biclustering. In: Frnti P, Brown G, Loog M, Escolano F, Pelillo M (eds) Structural, syntactic, and statistical pattern recognition, vol 8621. Lecture notes in computer science. Springer, Berlin, pp 394–403

Denitto M, Farinelli A, Figueiredo MA, Bicego M (2017) A biclustering approach based on factor graphs and the max-sum algorithm. Pattern Recognit 62:114–124CrossRef

Dhillon I (2001) Coclustering documents and words using bipartite spectral graph partitioning. In: Proceedings of international conference on knowledge discovery and data mining, pp 269–274

Dolnicar S, Kaiser S, Lazarevski K, Leisch F (2012) Biclustering: overcoming data dimensionality problems in market segmentation. J Travel Res 51(1, (1)):41–49CrossRef

Farhi E, Goldstone J, Gutmann S (2002) Quantum adiabatic evolution algorithms versus simulated annealing. Eprint arXiv:quant-ph/0201031

Finnila AB, Gomez MA, Sebenik C, Stenson C, Doll JD (1994) Quantum annealing: a new method for minimizing multidimensional functions. Chem Phys Lett 219:343–348CrossRef

Flores JL, Inza I, Larranaga P, Calvo B (2013) A new measure for gene expression biclustering based on non-parametric correlation. Comput Methods Programs Biomed 112(3):367–397CrossRef

Frey BJ, Dueck D (2007) Clustering by passing messages between data points. Science 315(5814):972–976MathSciNetCrossRefMATH

Henriques R, Madeira SC (2014) BicPAM: pattern-based biclustering for biomedical data analysis. Algorithms Mol Biol 9(1):27CrossRef

Henriques R, Madeira SC (2018) BSig: evaluating the statistical significance of biclustering solutions. Data Min Knowl Disc 32(1):124–161. https://doi.org/10.1007/s10618-017-0521-2 MathSciNetCrossRef

Henriques R, Antunes C, Madeira SC (2015) A structured view on pattern mining-based biclustering. Pattern Recognit 48(12):3941–3958CrossRef

Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58(5):5355–5363CrossRef

King J, Yarkoni S, Raymond J, Ozfidan I, King AD, Nevisi MM, Hilton JP, McGeoch CC (2017) Quantum annealing amid local ruggedness and global frustration. ArXiv e-prints arXiv:1701.04579

Kochenberger G, Hao J, Glover F, Lewis M, Lü Z, Wang H, Wang Y (2014) The unconstrained binary quadratic programming problem: a survey. J Comb Optim 28(1):58–81MathSciNetCrossRefMATH

Kurihara K, Tanaka S, Miyashita S (2009) Quantum annealing for clustering. In: Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence. UAI ’09. AUAI Press, Arlington, pp 321–328

Madeira S, Oliveira A (2004) Biclustering algorithms for biological data analysis: a survey. IEEE Trans Comput Biol Bioinform 1:24–44CrossRef

Mukhopadhyay A, Maulik U, Bandyopadhyay S, Coello C (2014) Survey of multiobjective evolutionary algorithms for data mining: part II. IEEE Trans Evolut Comput 18(1):20–35CrossRef

Neven H, Rose G, Macready WG (2008) Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization, ArXiv e-prints arXiv:0804.4457

Oghabian A, Kilpinen S, Hautaniemi S, Czeizler E (2014) Biclustering methods: biological relevance and application in gene expression analysis. PLoS ONE 9(3):e90,801CrossRef

O’Gorman B, Babbush R, Perdomo-Ortiz A, Aspuru-Guzik A, Smelyanskiy V (2015a) Bayesian network structure learning using quantum annealing. Eur Phys J Spec Top 224(1):163–188CrossRef

O’Gorman B, Rieffel E, Do M, Venturelli D, Frank J (2015b) Compiling planning into quantum optimization problems: a comparative study. In: Proceedings of the workshop on constraint satisfaction techniques for planning and scheduling problems (COPLAS-15), pp 11–20

Perdomo-Ortiz A, Fluegemann J, Biswas R, Smelyanskiy VN (2015) A performance estimator for quantum annealers: Gauge selection and parameter setting. ArXiv e-prints arXiv:1503.01083

Prelić A, Bleuler S, Zimmermann P, Wille A, Bühlmann P, Gruissem W, Hennig L, Thiele L, Zitzler E (2006) A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics 22(9):1122–1129CrossRef

Pudenz KL (2016) Parameter setting for quantum annealers. In: 2016 IEEE high performance extreme computing conference (HPEC), pp 1–6

Ray P, Chakrabarti BK, Chakrabarti A (1989) Sherrington–Kirkpatrick model in a transverse field: absence of replica symmetry breaking due to quantum fluctuations. Phys Rev B 39:11,828–11,832CrossRef

Rieffel EG, Venturelli D, O’Gorman B, Do MB, Prystay EM, Smelyanskiy VN (2015) A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf Process 14:1–36 arXiv:1407.2887 CrossRefMATH

Santoro GE, Tosatti E (2006) Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J Phys A Math Gen 39(36):R393–R431MathSciNetCrossRefMATH

Truong DT, Battiti R, Brunato M (2013) A repeated local search algorithm for biclustering of gene expression data. In: Hancock E, Pelillo M (eds) Similarity-based pattern recognition. Springer, Heidelberg, pp 281–296. https://doi.org/10.1007/978-3-642-39140-8_19

Tu K, Ouyang X, Han D, Honavar V (2011) Exemplar-based robust coherent biclustering. In: SDM, SIAM, pp 884–895

Venturelli D, Mandrà S, Knysh S, O’Gorman B, Biswas R, Smelyanskiy V (2015) Quantum optimization of fully connected spin glasses. Phys Rev X 5(031):040

Yang J, Wang H, Wang W, Yu PS (2005) An improved biclustering method for analyzing gene expression profiles. Int J Artif Intell Tools 14(05):771–789CrossRef

Title: Biclustering with a quantum annealer
Authors: Lorenzo Bottarelli
Manuele Bicego
Matteo Denitto
Alessandra Di Pierro
Alessandro Farinelli
Riccardo Mengoni
Publication date: 29-01-2018
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 18/2018
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3034-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 18/2018

Handling dropout probability estimation in convolution neural networks using meta-heuristics

Arithmetic and parent-centric headless chicken crossover operators for dynamic particle swarm optimization algorithms

Elephant search algorithm applied to data clustering

Prediction of generated power from steam turbine waste heat recovery mechanism system on naturally aspirated spark ignition engine using artificial neural network

Wikipedia-based hybrid document representation for textual news classification

Solving binary cutting stock with matheuristics using particle swarm optimization and simulated annealing

Premium Partner