在本節(jié)中，我們將闡述八種應(yīng)用在單細胞轉(zhuǎn)錄組數(shù)據(jù)的聚類方法，并總結(jié)了這些方法的優(yōu)點、局限性和時間復雜度等。一部分單細胞聚類的工具會使用多種聚類算法，因此會在多個類別中列出。

01

基于劃分的聚類

基于劃分的聚類方法主要是確定最佳的K個中心，將數(shù)據(jù)點劃分為K個簇，其中心要么是質(zhì)心（均值），稱為k-means，要么是中心點，稱為k-medoids。 k-means方法的思想是找到質(zhì)心，以最小化每個數(shù)據(jù)點與其最近質(zhì)心之間的歐氏距離的平方和。它具有時間復雜度低的優(yōu)點。但是，它對異常值很敏感，并且用戶必須預(yù)先指定聚類的數(shù)量K。對于將N個D維數(shù)據(jù)點聚為K個類，使用Lloyd 's算法的k-means每次迭代的時間復雜度為O(KND)。 以下是一些使用k-means聚類的單細胞轉(zhuǎn)錄組數(shù)據(jù)分析工具。SAIC在迭代聚類過程中使用k-means并結(jié)合ANOVA識別特征基因；SCUBA使用k-means將每個時間點的細胞分為兩組，并使用間隔統(tǒng)計量來識別分叉事件；SC3的步驟之一是在細胞距離矩陣上使用k-means聚類（圖3）。k-medoids方法是將原始N個數(shù)據(jù)點中的K個數(shù)據(jù)點識別為中心點，以最小化數(shù)據(jù)點到中心點的距離之和。它非常適用于以有意義的中心點作為聚類中心的離散數(shù)據(jù)。然而，與k-means類似，它對異常值很敏感，用戶必須預(yù)先指定聚類的數(shù)量K。對于從N個數(shù)據(jù)點中選擇最優(yōu)K個點的組合問題，采用圍繞中心點劃分算法的k-medoids的時間復雜度為O(K(N?K)2)。

Figure 3. SC3聚類流程圖

RaceID2用于利用單細胞轉(zhuǎn)錄組數(shù)據(jù)識別罕見細胞類型，結(jié)果表明用k-medoids取代k-means方法進行聚類可以明顯改善聚類的結(jié)果。

02

層次聚類

次聚類是基因表達數(shù)據(jù)分析中應(yīng)用最廣泛的聚類方法。層次聚類在數(shù)據(jù)點之間構(gòu)建層次結(jié)構(gòu)，它根據(jù)層次樹中的分支定義不同的類群。許多單細胞轉(zhuǎn)錄組數(shù)據(jù)的聚類算法都是基于層次聚類或?qū)哟尉垲愖鳛榉治龅牟襟E之一。

層次聚類對數(shù)據(jù)本身的分布并沒有過多要求，因此，它適用于許多不同形狀的數(shù)據(jù)集；層次聚類的另一個優(yōu)點是通過數(shù)據(jù)點之間的層次關(guān)系，可以用于發(fā)現(xiàn)其內(nèi)在的關(guān)聯(lián)，有助于對結(jié)果的解釋。層次聚類主要有兩種實現(xiàn)方法：聚合式（agglomerative）和分裂式（divisive）。 聚合式又叫“自下而上式（bottom-up）”的聚類，它從N個數(shù)據(jù)點開始，每一個數(shù)據(jù)點作為一個單獨的類，在每一步中，類群依據(jù)它們之間的距離進行合并，直到所有類群在層次結(jié)構(gòu)的根處合并在一起。分裂式又叫“自上而下式（top-down）”聚類，相比之下，該方法首先將所有數(shù)據(jù)點當成一個類群，然后每一步遞歸劃分更小的類群，直到分成N個類群為止。無論是哪一種，層次聚類的一個顯著缺點是時間復雜度高，運行時間非常久。此外，層次關(guān)系并不能提供數(shù)據(jù)點的最佳聚類劃分，還需要一個額外的步驟來從層次樹中決定最終劃分的類群數(shù)量。 BackSPIN是一種雙聚類算法，分別在細胞和基因的維度上應(yīng)用層次聚類。BackSPIN使用SPIN迭代地拆分基因表達矩陣，直到在分支處不再滿足拆分標準；cellTree通過在話題分布上構(gòu)造最小生成樹，從而在單個細胞之間構(gòu)建層次結(jié)構(gòu)；CIDR對PCoA獲得的低維嵌入使用了層次聚類；ICGS采用層次聚類，將篩選后得到的一組基因的表達數(shù)據(jù)按表達水平和動態(tài)范圍進行聚類，并進行配對相關(guān)分析；SC3對多個k-means聚類結(jié)果合并得到的一致性矩陣進行層次聚類；為了獲得層次結(jié)構(gòu)中的實際類群，DendroSplit通過衡量與原始表達數(shù)據(jù)的分離分數(shù)，使用動態(tài)拆分和合并分支來檢測層次樹中的類群。

03

混合模型

混合模型聚類基于的假設(shè)思想是，數(shù)據(jù)點是從幾個混合的概率分布中采樣，每個概率分布代表一個聚類。樣本的聚類是通過從每個分布中學習其生成的概率來推斷的。用于聚類的常見混合模型主要包括應(yīng)用于連續(xù)型數(shù)據(jù)的高斯混合模型（GMM）和計數(shù)型數(shù)據(jù)的分類混合模型。

混合模型的優(yōu)點包括嚴格的概率建模和在模型中引入先驗知識的靈活性。然而，解決混合模型需要先進的優(yōu)化或采樣技術(shù)，具有較高的計算復雜度，并依賴于關(guān)于數(shù)據(jù)分布的假設(shè)的準確性。混合模型通常是用期望最大算法學習的，它可以推斷混合參數(shù)和類分配似然性，也可以用抽樣和變分方法學習圖概率模型。此外，混合模型的時間復雜度取決于混合的分布，比如在GMM中，時間復雜度為O(N2K)。 BISCUIT基于層次狄利克雷過程混合模型（HDMM），并附加細胞特定的標準化和dropouts矯正。它的過程首先是應(yīng)用HDMM對細胞建模，形成包含Dirichlet先驗的混合系數(shù)、均值、Wishart先驗的協(xié)方差矩陣的高斯混合模型，而細胞特定的縮放因子代表了技術(shù)變異。早先版本的Seurat能夠?qū)渭毎D(zhuǎn)錄組數(shù)據(jù)與原位RNA測序相結(jié)合，用于單細胞的空間聚類。在雙峰混合模型中，針對一組選定的標志基因，將單細胞轉(zhuǎn)錄組數(shù)據(jù)與二值化的原位RNA數(shù)據(jù)整合，然后通過雙峰混合模型中單細胞轉(zhuǎn)錄組表達譜的后驗概率將每個單細胞分配到不同的空間類群區(qū)域。

04

基于圖的聚類

在基于圖的聚類中，數(shù)據(jù)點被表示為圖（Graph）中的節(jié)點，而節(jié)點間的邊（Edge）由數(shù)據(jù)點之間的相似性表示?；趫D的聚類基于一個簡單的假設(shè)，即圖中的密集社區(qū)（community）表示為密集的子圖或譜成分，因此對于數(shù)據(jù)的分布并沒有過于依賴。兩種最常用的圖聚類算法是譜聚類和團（clique）發(fā)現(xiàn)。

在譜聚類中，通過相似函數(shù)（如RBF核函數(shù)）建立相似性矩陣及其拉普拉斯圖。通過計算拉普拉斯圖的頂部特征向量，以便后續(xù)的k-means聚類。雖然可以使用更有效的方法來尋找固定數(shù)量的頂部特征向量，但尋找所有特征向量的時間復雜度為O(N3)，因此，譜聚類并不適用于大數(shù)據(jù)集。當細胞類型作為先驗已知時，基于TCC的聚類利用細胞間的Jensen-Shannon距離構(gòu)建相似性矩陣進行譜聚類；未知時則應(yīng)用近鄰傳播聚類。 在圖論中，團被定義為每對節(jié)點都相鄰的子圖，因此，團代表了圖中數(shù)據(jù)點的類群。由于在圖中找到團是一個NP-hard問題，通常會使用啟發(fā)式方法。SNN-Cliq利用單細胞轉(zhuǎn)錄組數(shù)據(jù)對細胞進行團簇檢測。在稀疏圖中團通常很少見，因此，SNN-cliq在SNN圖中檢測到的團一般是密集但是不完全連通的。

Figure 4. Louvain算法示意圖

另一種常用于單細胞分析的基于圖聚類的算法是Louvain算法（圖4）。Louvain是一種社區(qū)檢測算法，它比其他基于圖的算法更具可擴展性，通過貪婪方式將節(jié)點分配給社區(qū)，并更新網(wǎng)絡(luò)以獲得低分辨率的聚類。Louvain的時間復雜度為O(NlogN)。Scanpy是一個集成了Louvain算法、提供了一個能夠分析大規(guī)模單細胞轉(zhuǎn)錄組數(shù)據(jù)集的工具。Seurat在默認情況下也是利用Louvain算法在細胞SNN圖上來發(fā)現(xiàn)細胞類型。

05

基于密度的聚類

基于密度的聚類將類群定義為一個空間中具有高密度數(shù)據(jù)點的區(qū)域。DBSCAN和密度峰值聚類是基于密度的聚類的兩個例子。

給定一個數(shù)據(jù)點，將其作為中心以ε為半徑劃分出一個球形，球形內(nèi)的數(shù)據(jù)點數(shù)量如果超過指定的閾值，那么這些數(shù)據(jù)點就被DBSCAN認為是一個類群。對每個數(shù)據(jù)點重復該過程，不斷擴展，最終完成聚類。該方法具有效率高、適用于任何形狀的數(shù)據(jù)的優(yōu)點。然而，密度聚類對參數(shù)非常敏感，如果類群密度不平衡，結(jié)果會非常差。DBSCAN聚類的時間復雜度為O(NlogN)?；诿芏鹊木垲愅ǔＳ糜趩渭毎D(zhuǎn)錄組數(shù)據(jù)分析中的異常細胞識別，如GiniClust和Monocle2。 GiniClust是基于DBSCAN來發(fā)現(xiàn)罕見的細胞亞群，它使用基尼指數(shù)作為基因表達值變異性的衡量標準，以篩選高變基因，然后由DBSCAN對細胞聚類。密度峰值聚類考慮數(shù)據(jù)點之間的距離，而不是像DBSCAN那樣考慮密度閾值，同時假設(shè)聚類的中心是聚類中數(shù)據(jù)點密度的局部最大值。密度峰值聚類的時間復雜度為O(N2)。在Monocle2中，就是對t-SNE空間內(nèi)的細胞進行密度峰值聚類。

06

神經(jīng)網(wǎng)絡(luò)

Kohonen神經(jīng)網(wǎng)絡(luò)，也稱為自組織特征映射神經(jīng)網(wǎng)絡(luò)（SOMs），運用競爭學習策略逐步優(yōu)化網(wǎng)絡(luò)進行聚類，使用隨機梯度下降通過不斷迭代訓練數(shù)據(jù)點和每個中心的相似度來更新聚類中心。類群中心使用預(yù)定義的結(jié)構(gòu)（如網(wǎng)格）進行初始化。SOM具有相當強的可擴展性，因為隨機梯度下降不需要把所有的數(shù)據(jù)點保存在計算機內(nèi)存中。此外，中心之間的預(yù)定義結(jié)構(gòu)可以引入先驗知識，并在類群之間提供可解釋的關(guān)系。然而，SOM對參數(shù)異常敏感，比如用于更新權(quán)重的學習率。

SOM也已用于單細胞轉(zhuǎn)錄組數(shù)據(jù)的可視化和聚類。在一些研究中應(yīng)用SOM在二維熱圖中直觀的可視化相似關(guān)系。SCRAT為用戶提供了可視化二維熱圖的選項，該熱圖反映了跨細胞群的基因之間的相關(guān)性。SOMSC利用SOM將高維基因表達數(shù)據(jù)折疊成二維，用于識別處于中間過渡狀態(tài)的細胞以及擬時間排序。

07

集成聚類

集成聚類，也稱為共識聚類，是一種廣泛使用的策略。在該策略中，通過不同的應(yīng)用場景（例如不同的聚類算法，相似的度量和特征選擇/映射等）對同一數(shù)據(jù)集進行聚類，然后基于單個聚類結(jié)果之間的一致性，通過共識函數(shù)對它們進行合并。集成學習可以捕獲不同數(shù)據(jù)或聚類模型中的多樣性，并且已被證明比單一模型更健壯，并產(chǎn)生更好的結(jié)果。集成聚類的局限性是依賴于其他的數(shù)據(jù)轉(zhuǎn)換和基本聚類方法。

SC3是一種用于單細胞轉(zhuǎn)錄組數(shù)據(jù)聚類的共識聚類方法。SC3首先通過三種不同的度量（斯皮爾曼、皮爾森和歐氏距離）來計算細胞間相似性，然后使用PCA和拉普拉斯轉(zhuǎn)換進行分解，通過k-means對不同類型的低維嵌入進行聚類，接著用CSPA共識函數(shù)構(gòu)建一致性矩陣，最后，利用該矩陣進行層次聚類。conCluster是另一種共識聚類方法，它使用多個不同的參數(shù)通過t-SNE和k-means進行了組合，然后將這些不同的組合連接起來，用于最后的k-means聚類。

08

近鄰傳播聚類

該聚類方法的主要思想是通過不同點之間的信息傳遞來選擇聚類中心：吸引度（responsibility）用于描述一個數(shù)據(jù)點k作為數(shù)據(jù)點i的聚類中心的適合程度；歸屬度（availability）則描述了數(shù)據(jù)點i選擇數(shù)據(jù)點k作為聚類中心的適合程度。近鄰傳播聚類的主要優(yōu)點是不需要知道類群的數(shù)量。缺點是時間復雜度較高，對異常值敏感。當細胞類型數(shù)量未知時，基于TCC的聚類以該方式進行細胞的聚類。在SIMLR中也選項可以選擇對數(shù)據(jù)進行該方法的聚類。

Table 1聚類方法的分類及優(yōu)缺點

審核編輯 ：李倩