Quantum annealing-based clustering of single cell RNA-seq data

Cluster analysis is a crucial stage in the analysis and interpretation of single-cell gene expression (scRNA-seq) data. It is an inherently ill-posed problem whose solutions depend heavily on hyper-parameter and algorithmic choice. The popular approach of K-means clustering, for example, depends heavily on the choice of K and the convergence of the expectation-maximization algorithm to local minima of the objective. Exhaustive search of the space for multiple good quality solutions is known to be a complex problem.

University of Southampton researchers show that quantum computing offers a solution to exploring the cost function of clustering by quantum annealing, implemented on a quantum computing facility offered by D-Wave. Out formulation extracts minimum vertex cover of an affinity graph to sub-sample the cell population and quantum annealing to optimise the cost function. A distribution of low-energy solutions can thus be extracted, offering alternate hypotheses about how genes group together in their space of expressions.

Quantum annealing-based clustering of the sub-sampled graph

The graph on the left represents a solution to the minimum vertex cover implemented on the QA. Yellow nodes correspond to the selected sub-graph. The graph on the right depicts partitioning of the SNN graph defined on the selected subset of nodes.

Availability – Code, including data cleaning, pre-processing, different quantum annealing implementations and data visualisation, is published on GitHub: https://github.com/michal7kw/scRNA-seq-Clustering-QA.git.