Nature Method:Rob Knight发布Striped UniFrac算法轻松分析微生物组大数据

Striped UniFrac微生物组大尺度分析算法

Striped UniFrac: enabling microbiome analysis at unprecedented scale

Nature Methods, [IF 26.919], correspondence, 2018-10-30

第一作者:Daniel Mcdonald

通讯作者:Rob Knight

主要单位:加州大学圣地亚哥分校,儿科,计算科学与工程系,微生物组创新中心,生物工程系

大佬们都是身兼数职,一个人就挂了四个通讯单位,还好都是一个单位的。

其它作者:Yoshiki Vázquez-Baeza, David Koslicki, Jason McClelland, Nicolai Reeve, Zhenjiang Xu, Antonio Gonzalez

如果你对微生物组分析不了解,或不认识Rob Knight,一定仔细阅读下文补补基础知识

简介

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发文推出改进版本,大幅提高性能,使空前规模的大样本分析成为可能。

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20190702A00C2R00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券