背景&思想

PhenoGraph算法的輸入是一個N X D的矩陣， 把這個矩陣中的行劃分到類別中，使得類別間的差異大于類別內(nèi)的差異。

我們的假設是，這些類別代表具有生物學意義表型的細胞群。我們的前提假設是細胞群聚集在D維空間的密集區(qū)域，由緊密Marker表達組合定義。因此，我們的目標是在D維空間中辨別這些密集的細胞區(qū)域。然而，我們不知道數(shù)據(jù)中類別的數(shù)量，大小或高維形狀（例如，橢球，凸）。 單細胞域（domain）特別具有挑戰(zhàn)性，因為不同類別之間，類別大小可能會有數(shù)量級上的差異（例如，造血干細胞與T細胞），并且我們希望識別罕見子集（類別）而不是將它們作為離群點而丟棄。此外，雖然大多數(shù)聚類算法都假設類別內(nèi)樣本分布近似橢球形，但我們已經(jīng)證明許多細胞亞類具有復雜的形狀并且不一定是凸形的（viSNE enables visualization of high dimensional single-cell data and reveals phenotypic heterogeneity of leukemia. Nat Biotechnol. 2013）。 用于密度檢測的參數(shù)方法需要關于細胞群體（例如，橢球，凸）的形狀的強依賴性假設，而單細胞數(shù)據(jù)中通常不符合這樣的假設。

為了克服這些障礙，我們構建了一個圖形結構來表示單細胞數(shù)據(jù)中細胞狀態(tài)的高維幾何結構。每個細胞作為節(jié)點并且通過邊連接到其鄰居細胞（與其最相似的細胞），該邊的權重由細胞之間的相似性設置。細胞在高維空間中的密集區(qū)域將在該圖中表現(xiàn)為高度互連的模塊，通過該模塊內(nèi)具有高密度的邊的特征來識別。一旦構建完畢，該圖可以被劃分成這些緊密互連的模塊的子集，稱為群體（communities），代表不同的表型亞群（類別）。這些圖中的群體（communities）的檢測（Community structure in social and biological networks. Proc. Natl. Acad. Sci. 2002）為識別亞群提供了一種高效方法。與混合模型等參數(shù)化方法不同，該方法不假設子群（某一類別）的大小、分布或數(shù)量。該方法成功的關鍵是構造一個圖形結構，這個圖形結構真實的表示D維空間中存在的幾何結構。PhenoGraph分兩步建立單細胞數(shù)據(jù)的圖結構。

步驟

第一步，使用歐式距離為每個細胞識別k個最近鄰居，其中k是該方法的唯一參數(shù)；如果k值太大，較小的群體（communities）會受到其他節(jié)點的影響，難以被識別出來。而如果，k值太小會導致我們想要找的細胞群體內(nèi)緊密度較差。

因此，在第二步中，我們改進了第一步中定義的k鄰居。對所有細胞的k近鄰搜索的結果是一組集合：N組k鄰居。我們對這些集合進行操作以建立一個加權圖。在這個圖中，每對節(jié)點（細胞）之間的權重是基于它們共享的鄰居的數(shù)量。

節(jié)點i和j之間的權重由以下公式給出：

其中v(i)是節(jié)點i的k鄰居；v(j)是節(jié)點j的k鄰居。

以這種方式由真實數(shù)據(jù)構造的圖具有明顯的模塊化結構。

群體（communities）檢測是指將節(jié)點劃分成不同的群體（communities），從而捕獲這個模塊化結構。對于一組群體（communities）的確定C={c_(1,) c_(2,),…,c_k}，模塊系數(shù)Q的定義由下面公式確定:

其中Wij是節(jié)點i，j的邊權重，si是節(jié)點i與其他所有節(jié)點的邊權重加和，sj同上，ci是節(jié)點i所在的群體（communities），如果u=v，Kronecker delta 函數(shù)δ(u,v)=1；否則為0，m=1/2 ∑?W_ij 是一個標準化常數(shù)。

模塊系數(shù)Q介于-1到1之間，對于任意一個確定了群體（communities）圖結構都可以計算這么一個指標。所以該指標可以作為客觀衡量把圖結構區(qū)分成子集的質量。這樣，該問題就轉化成一個組合優(yōu)化問題，即NP完全問題。

接下來用Louvain方法（Fast unfolding of communities in large networks. J. Stat. Mech. 2008）來解決上述問題。Louvain方法具體步驟是，在第一次迭代時，每一個節(jié)點（細胞）被單獨作為一類（一個群體），在每一次迭代時，若兩個節(jié)點的合并能使得模塊系數(shù)Q有最大的增長，那么將這兩個節(jié)點合并成一類。直到模塊系數(shù)Q不再增加為止。

REF: Data-Driven Phenotypic Dissection of AML Reveals Progenitor-like Cells that Correlate with Prognosis. 2015 Cell.

群體（communities）檢測過程中的Resolution的限制

檢測群體（communities）結構對于發(fā)現(xiàn)復雜網(wǎng)絡中結構與功能之間的聯(lián)系以及生物學和社會學等許多學科的實際應用至關重要?，F(xiàn)在廣泛使用的一種流行方法依賴于對模塊的數(shù)量的優(yōu)化，這是將網(wǎng)絡劃分為群體（communities）的質量指標。我們發(fā)現(xiàn)，即使在模塊定義明確的情況下，模塊化優(yōu)化也可能無法識別小于一定規(guī)模的模塊，該模塊的規(guī)模取決于網(wǎng)絡的總大小和模塊的互連程度。Newman和Girvan（Finding and evaluating community structure in networks. Physical review E, 2004.）在群體（communities）檢測方面取得了決定性的進展，他們引入了一種定量方法來衡量將網(wǎng)絡劃分為群體（communities）的質量，即模塊化。該度量實質上將給定模塊內(nèi)的連接數(shù)與相同大小和相同度數(shù)序列的隨機圖的期望值進行比較。如果選擇模塊化作為相關質量函數(shù)，則群體（communities）檢測的問題就等同于模塊化優(yōu)化。后者非常重要，因為將網(wǎng)絡劃分為群體（communities）的可能性至少隨著網(wǎng)絡的大小呈指數(shù)增長，即使對于較小的圖，窮舉式優(yōu)化在計算上也不可行。我們表明模塊化優(yōu)化確實不能解決大數(shù)量的模塊。因此，有必要對通過模塊化優(yōu)化獲得的模塊進行檢查。我們表明，模塊化存在一個固有規(guī)模，該規(guī)模取決于網(wǎng)絡中邊的總數(shù)。小于此規(guī)模的模塊可能無法解析，即使在極端情況下，它們是通過單橋連接的完整圖形。模塊化分辨率的極限實際上取決于群體（communities）對之間的互連程度，并且可以達到整個網(wǎng)絡大小的數(shù)量級。因此，事先無法確定通過模塊化優(yōu)化檢測到的模塊（大還是小）確實是單個模塊還是多個較小模塊的集合。然而，最大模塊性因網(wǎng)絡的不同而不同，并且取決于網(wǎng)絡的連接數(shù)。我們證明了任何網(wǎng)絡的模塊性值的上限都是1，并且我們看到模塊性是與網(wǎng)絡尺度相關的。

REF: Resolution limit in community detection. 2007 PNAS.

Seurat包中的PhenoGraph方法實現(xiàn)

函數(shù)FindClusters

FindClusters(object, modularity.fxn = 1, initial.membership = NULL, weights = NULL, node.sizes = NULL,? resolution = 0.8, algorithm = 1, n.start = 10, n.iter = 10, random.seed = 0, group.singletons = TRUE, temp.file.location = NULL, edge.file.name = NULL, verbose = TRUE, ...)

參數(shù)

#object: Seurat Object

#modularity.fxn: 計算模塊系數(shù)函數(shù)，1為標準函數(shù)；2為備選函數(shù)，這里沒有具體說明是什么函數(shù)，我認為1是上面提到的Kronecker delta函數(shù)。

# resolution: 分辨率參數(shù)，如果大于1，則會得到較多數(shù)目的群體（communities）；如果小于1，則會得到較少數(shù)目的群體（communities）。

#algorithm: 模塊系數(shù)優(yōu)化算法，1使用原始Louvain算法；2使用Louvain algorithm with multilevel refinement；3使用SLM算法；4使用Leiden算法（注：4需要額外安裝插件）

#n.start: 隨機開始的數(shù)量

#n.iter: 最大迭代次數(shù)

#random.seed: 隨機數(shù)種子

#graph.name: 圖的名字

#group.singletons: (TRUE/FALSE)是否把比較特異的細胞分配到最近的類別中，若FALSE，則可能會出現(xiàn)某個類只有一個細胞的情況

#verbose: 是否在控制臺輸出結果