背景&思想

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ū)域?qū)⒃谠搱D中表現(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ū)分成子集的質(zhì)量。這樣癞埠，該問題就轉(zhuǎn)化成一個組合優(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)系以及生物學和社會學等許多學科的實際應用至關重要。現(xiàn)在廣泛使用的一種流行方法依賴于對模塊的數(shù)量的優(yōu)化吧黄，這是將網(wǎng)絡劃分為群體（communities）的質(zhì)量指標部服。我們發(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）的質(zhì)量剧蹂，即模塊化。該度量實質(zhì)上將給定模塊內(nèi)的連接數(shù)與相同大小和相同度數(shù)序列的隨機圖的期望值進行比較烦却。如果選擇模塊化作為相關質(zhì)量函數(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: 是否在控制臺輸出結果