Striped UniFrac微生物組大尺度分析算法
Striped UniFrac: enabling microbiome analysis at unprecedented scale
Nature Methods, [IF 26.919], correspondence, 2018-10-30
DOI: http://dx.doi.org/10.1038/s41592-018-0187-8
第一作者：Daniel Mcdonald
主要單位：加州大學聖地亞哥分校，兒科，計算科學與工程系，微生物組創新中心，生物工程系
大佬們都是身兼數職，一個人就掛了四個通訊單位，還好都是一個單位的。
其它作者：Yoshiki Vázquez-Baeza, David Koslicki, Jason McClelland, Nicolai Reeve, Zhenjiang Xu, Antonio Gonzalez
如果你對微生物組分析不瞭解，或不認識Rob Knight，一定仔細閱讀下文補補基礎知識
Nature綜述：大佬手把手教你分析菌群數據
簡介
UniFrac是一種基於進化關係信息，計算樣本間距離並進行微生物群體間的比較的方法，2005年由Rob Knight提出，截止2018年11月1日引用3762次。
此方法也在不段改進，2006推出在線工具，2010年提高計算速度，此方法最高引的4篇文章全是Rob Knight出品，共引用6609次。
近年來測序成本的下降，項目的規模越來越大，動輒成千上萬的樣本計算UniFrac距離進還是非常費時費力的，經常一兩天沒有結果，已經無法滿足當前大規模數據分析的要求。
因為距離矩陣計算時，計算量和內存消耗隨樣本量增長呈幾何積數增長；如10樣品計算矩陣為100次，而1000樣則為1,000,000次；時間和內存消耗增長10,000倍，對目前的計算資源是無法接受。如果能把算法優化為線性增加內存和計算量，就不再可怕了。
今天Rob Knight在Nature Method發佈了改進版的UniFrac算法——條形UniFrac(Striped UniFrac，我理解Striped即為轉換矩陣計算為條形向量計算之意)，計算量和內存消耗僅與樣本量成線性關係，完美解決了大數據計算難的問題。
導讀
Rob Knight發表的基於進化距離UniFrac算法在微生物組領域使用廣泛，引用超6千次；
近年來微生物組項目動輒成千上萬的樣本量，UniFrac算法對計算時間和內存消耗隨樣本量呈幾何級數增長，很多大項目幾乎無法完成此分析；
作者提出新的條形UniFrac方法，結果保持不變，優化計算資源消耗與樣本量呈線性關係，並極大的降低內存和時間消耗，如計算EMP的2萬個樣本的時間可由幾個月縮短至1天內；
方法提供命令行工具，並己整合至分析流程QIIME2和在線平臺Qiita，方便同行使用。
正文
UniFrac度量在微生物組研究中應用廣泛，但它並不適合當今的大數據集(計算過幾千個樣本的人，都感受過此步慢的出奇)。我們提出新算法，條形UniFrac，與原來計算結果一致，卻極大的減少了內存和計算資源的消耗。同時發佈了C語言共享庫方便其它程序調用(https://github.com/biocore/unifrac)
UniFrac是基於進化距離的方法，進行微生物組成樣本成對比較。現階段，微生物組研究經常包括上千的樣本，如地球微生物組計劃(EMP)的27,751個樣本，人類腸道計劃的15,096個樣本。現有的算法在有限的時間和空間上無法完成以上項目的分析，即使使用快速的UniFrac算法，計算EMP項目也需要幾個月時間。條形UniFrac產生與現有方法一致的結果，但可提高單線程
30倍的效率，同時計算量與樣本數量呈線性關係，可在筆記本上24小時完成EMP項目的計算。這使科學家挖掘EMP和美國腸道計劃中新的生物學觀點成為可能。為演示算法的效率，我們計算QIITA中公開的113,721個樣本，採用256核計算時間小於48小時。
條形UniFrac的優勢是改進了空間複雜度，通過後序遍歷累計連續的度量，轉換成對比較的比例向量。
圖1. 算法描述和性能評估結果
a. 進化樹中某個節點，樣本比例內嵌導致比例信息被複制。樣本比例複製的重複模擬旋轉，可以在連續的內存中計算成對的距離。
b. 四樣本邏輯距離矩陣的雙條形顯示圖；條上的標籤代表成對比較，如AB代表樣本A和樣本B的距離。
c,d, 比較有權重末標準化的UniFrac使用phyloseq， QIIME1.9.1， scikit-bio(skbio), 條形UniFrac快速模式(SU-fast), 條形Unifrac精確模式(SU-exact)經驗時間(c)和內存(d)消耗。使用EMP 90-nt(317,314個唯一的Deblur sub-OTUs)，每個數據點代表10次獨立實驗的均值。所有分析運行於單線程、非共享的計算結點，並且沒有運行其它計算任何。任何在超過24h或大於256GB內存時被殺死。誤差線表示95%置信區間。原始數據見補充數據2。
在快速UniFrac中後序聚合移除了主導的量化因子以降低空間複雜度(附圖1c,d)。向量旋轉(Vector rotation，在圖1a表示為內嵌embedding)允許編繹器使用單說明的多數據操作(SIMD)。旋轉後，成對的距離沿著對角線計算(圖1b)，可以使用更多緩存、任務並行和硬件層面的預讀文件。同時引入了啟發式搜索來忽略進化樹的末端，可以減少50%的計算量(相關與準確性的計算見附圖1e)。對條形UniFrac算法與現有方法比較結果見圖1c，d，其性能遠超當前現有方法。
如何使用
條形UniFrac算法的代碼發佈於GitHub (https://github.com/biocore/unifrac)。
該方法目前也已經整理到QIIME2流程中
也可以在Qiita雲平臺中使用。
算法也有命令行版本可用，同時提供了C語言共享庫，和Python應用程序的界面。
熱心腸導讀
Rob Knight發佈條形UniFrac算法輕鬆分析微生物組大數據
原標題：條形UniFrac算法可分析空前規模的微生物組大數據
① UniFrac 算法在微生物組領域引用超6千次；
② UniFrac 算法對計算時間和內存消耗隨樣本量呈幾何級數增長，近年來微生物組項目動輒成千上萬的樣本量，很多大項目幾乎無法完成分析；
③ 作者提出新的條形 UniFrac 方法，結果保持不變，計算資源消耗與樣本量呈線性關係，並極大的降低內存和時間消耗，如計算EMP的2萬個樣本的時間可由幾個月縮短至1天內；
④ 方法提供命令行工具，並己整合至分析流程 QIIME2 和在線平臺 Qiita，方便同行使用。
主編評語：UniFrac是一種基於進化關係信息，計算樣本間距離並進行微生物群體間的比較的方法，2005年由Rob Knight提出。近日，作者在Nature Methods發文推出改進版本，大幅提高性能，使空前規模的大樣本分析成為可能。
閱讀更多 微生物組 的文章
