Faculty of Engineering and Physical Sciences, University of Southampton.
Brief Bioinform. 2023 Sep 22;24(6). doi: 10.1093/bib/bbad377.
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. Here, we 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 [1]. 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.
聚类分析是分析和解释单细胞基因表达 (scRNA-seq) 数据的关键阶段。它是一个固有不适定的问题，其解决方案严重依赖于超参数和算法的选择。例如，流行的 K-means 聚类方法严重依赖于 K 的选择和期望最大化算法对目标函数局部最小值的收敛性。众所周知，对多个高质量解决方案的空间进行穷尽搜索是一个复杂的问题。在这里，我们表明量子计算通过量子退火为探索聚类的代价函数提供了一种解决方案，该方法在 D-Wave [1] 提供的量子计算设施上实现。我们的公式通过提取相似性图的最小顶点覆盖来对细胞群体进行子采样，并通过量子退火来优化代价函数。因此，可以提取出一组低能量的解决方案，提供关于基因在其表达空间中如何分组的替代假设。
