單細(xì)胞降維
基于單細(xì)胞表達(dá)矩陣的降維方式有很多，例如UMAP，t-SNE，PCA等，而Diffusion Map是基于非線性的降維模式。對于單細(xì)胞表達(dá)譜而言，該降維方法有利于降維出“枝干形狀”的效果：
Diffusion Map
文中提到的URD軟件既是基于Diffusion Map算法而制作的，Diffusion Map又稱為擴(kuò)散映射，其原理是將空間距離轉(zhuǎn)換為一種狀態(tài)轉(zhuǎn)移的概率，從而確定隨機(jī)游走的方向，從而確定細(xì)胞發(fā)育軌跡
該算法分為確定細(xì)胞轉(zhuǎn)移方向（Markov矩陣）和降維（Markov矩陣特征值分解降維）兩塊
如圖所示，紅色為我們的目標(biāo)細(xì)胞，在目標(biāo)細(xì)胞周圍有一些細(xì)胞，那么Diffusion Map首先計(jì)算這些細(xì)胞兩兩之間的距離，進(jìn)而Affinity化，即如果兩個(gè)細(xì)胞距離較大，那么其概率就小，如果兩個(gè)細(xì)胞距離較小，那么其概率就大。再將其轉(zhuǎn)換為Markov矩陣，Markov矩陣表示某細(xì)胞向其他細(xì)胞轉(zhuǎn)移的概率，因此在網(wǎng)絡(luò)圖中，邊的權(quán)重可以用Markov矩陣中的元素表示：
如上圖所示，對于鄰近的幾個(gè)細(xì)胞來說，當(dāng)距離矩陣換算為Markov矩陣后，里面的元素代表細(xì)胞間轉(zhuǎn)移游走的概率，比方說M12代表cell_1向cell_2轉(zhuǎn)移的概率；M13代表cell_1向cell_3轉(zhuǎn)移的概率。距離遠(yuǎn)的細(xì)胞轉(zhuǎn)移概率比較小，距離近的細(xì)胞轉(zhuǎn)移概率比較大（參照下文的Markov矩陣）。
因此Markov矩陣表示細(xì)胞隨機(jī)轉(zhuǎn)移到方向，進(jìn)而特征值分解降維到二維即可看出細(xì)胞的軌跡
1.計(jì)算距離矩陣
那么我們的單細(xì)胞矩陣形如：
每一行代表一個(gè)基因（一共m個(gè)基因）。每一列代表一個(gè)細(xì)胞（一共n個(gè)細(xì)胞）。首先，該算法先計(jì)算兩兩細(xì)胞之間的距離，轉(zhuǎn)換為距離矩陣D：
2.Affinity
之后根據(jù)一些核函數(shù)，例如高斯核函數(shù)進(jìn)行轉(zhuǎn)化，這一步稱為Affinity，轉(zhuǎn)移后的矩陣簡稱為A矩陣，i 為行，j 為列，其中Dij代表上述的距離矩陣：
A矩陣如下：
3.標(biāo)準(zhǔn)化（Markov矩陣）
再之后將A矩陣按行標(biāo)準(zhǔn)化以后，轉(zhuǎn)化為Markov矩陣：
將Markov矩陣簡稱為M矩陣：
比方說，cell_1和cell_2對應(yīng)的值表示cell_1向cell_2轉(zhuǎn)移的概率；而Markov矩陣為實(shí)對稱矩陣，一定能分解為n個(gè)秩為1的方陣乘它們各自的特征值λ然后相加的結(jié)果
接著我們需要把M矩陣給對角化分解：
其中ψ1，ψ2.....ψn是ψ矩陣的行向量，ψ矩陣為特征向量矩陣
ψ矩陣為n×n的特征向量方陣
那么 t 表示多重轉(zhuǎn)移的次數(shù)，轉(zhuǎn)移多次后可以達(dá)到平穩(wěn)狀態(tài)；這個(gè)對角矩陣的主對角線表示的是M矩陣的特征值（這里只展示3個(gè)）：
此時(shí)重構(gòu)數(shù)據(jù)點(diǎn)new：
其中ψ1，ψ2.....ψn是ψ矩陣的行向量
容易得到：
ψ×M代表將特征向量重新做旋轉(zhuǎn)拉伸，變換后的特征向量帶有M矩陣的特征，即細(xì)胞間距離的特征。
特征向量指向的點(diǎn)代表每個(gè)細(xì)胞在高維空間所在的點(diǎn)，變換后的列向量為帶有細(xì)胞距離特征的新坐標(biāo)點(diǎn)
ψ矩陣為n×n的特征向量方陣
其中q1，q2.....qn為ψ矩陣的列向量，即特征向量；ψ1，ψ2.....ψn是ψ矩陣的行向量；由于M矩陣為實(shí)對稱矩陣，因此q1...qn相互正交(實(shí)對稱矩陣可以被正交對角化)
也就是重構(gòu)的新坐標(biāo)點(diǎn)矩陣等于特征向量矩陣乘Markov矩陣，對應(yīng)的元素是相等的，并以此作為新坐標(biāo)點(diǎn)，M矩陣表示的是兩兩cell的距離，其中ψ×M相當(dāng)于做拉伸旋轉(zhuǎn)變化，變換后表示每個(gè)細(xì)胞在高維空間的相對位置（相對坐標(biāo)）
個(gè)人認(rèn)為作者采用M矩陣的特征向量組來重構(gòu)坐標(biāo)是因?yàn)榉奖愫罄m(xù)的計(jì)算，個(gè)人感覺任意一組正交向量組都可以，因?yàn)榻稻S是依據(jù)特征值λ的大小來完成的，所以M矩陣的特征向量組是最好選擇
新構(gòu)造的矩陣為new表示的是每個(gè)細(xì)胞在對應(yīng)維度的坐標(biāo)：
其中λ的順序?yàn)閺拇蟮叫?，ψ矩陣為n×n的特征向量方陣，ψi 表示第 i 行向量；即第 i 行的特征向量。從某種意義上，此時(shí)的n仍然表示細(xì)胞個(gè)數(shù)，而假設(shè)我想降維到二維，那么我只需保留前兩個(gè)即可，即 i=1，2，那么每個(gè)細(xì)胞的坐標(biāo)既是二維的
這樣就完成了降維，那么Diffusion Map通過Markov隨機(jī)游走來判斷細(xì)胞轉(zhuǎn)移的方向，從而確定細(xì)胞軌跡的
小tip
這個(gè)tip是關(guān)于如何理解
這一個(gè)坐標(biāo)轉(zhuǎn)換公式的意義，我們不妨舉一個(gè)簡單的例子：
前面的是特征向量矩陣，后面的是M矩陣，正如我們所說的，M矩陣是一個(gè)實(shí)對稱矩陣，所以特征向量：q1，q2，q3是相互正交的，并且M×q與q轉(zhuǎn)置×M是等效的
我們不妨利用矩陣的乘法性質(zhì)畫出圖來觀察：
在高維空間里，三個(gè)細(xì)胞的相對位置如圖所示，假設(shè)cell_1坐標(biāo)為(a1,b1,c1)；cell_2坐標(biāo)為(a2,b2,c2)；cell_3坐標(biāo)為(a3,b3,c3)
那么我們知道，在三個(gè)細(xì)胞中，經(jīng)過計(jì)算q3向量的特征值λ3比較小（這是因?yàn)閝3向量的變化相當(dāng)于q1向量和q2向量較?。?，所以對應(yīng)只保留q1向量特征值λ1和q2向量特征值λ2，從而構(gòu)建二維坐標(biāo)，這樣就完成了由三維降至二維
盜圖傳送門：傳送門
