编辑推荐：
UniFrac是一种基于系统发育信息的微生物组样本间差异度量方法，但在现代数据集规模下扩展性较差。研究人员引入了一种名为DartUniFrac的算法，并提供了经图形处理单元（GPU）加速的近最优实现，其计算速度比UniFrac快最多三个数量级，可扩展至数百万个
UniFrac是一种基于系统发育信息的微生物组样本间差异度量方法，但在现代数据集规模下扩展性较差。研究人员引入了一种名为DartUniFrac的算法，并提供了经图形处理单元（GPU）加速的近最优实现，其计算速度比UniFrac快最多三个数量级，可扩展至数百万个样本（两两比较）和数十亿个分类单元。DartUniFrac将UniFrac与加权Jaccard相似度相关联，并利用草图算法实现快速计算。
论文解读：DartUniFrac——超大规模微生物组系统发育多样性分析的新范式
**研究背景与现存问题**
UniFrac是微生物组研究中应用最广泛的系统发育β多样性（phylogenetic beta-diversity）度量指标之一，已被超过15,000项研究采用，包括地球微生物组计划（Earth Microbiome Project, EMP）和美国肠道计划（American Gut Project, AGP）。该指标通过利用系统发育树的分支长度信息，在群落周转涉及远缘谱系时，通常比Bray-Curtis和Jaccard等非系统发育距离产生更强的组间分离效果，因此在微生物生态学研究中具有不可替代的地位。然而，UniFrac的计算复杂度与其适用范围存在根本矛盾：加权UniFrac的复杂度与世界中的分类单元数量成正比，且随样本数量呈平方增长。随着高通量测序技术的普及，单个项目即可产生数千个样本和数百万个分类单元，计算所有样本间的两两UniFrac距离已成为实际应用中的主要瓶颈。过去20年间虽有大量优化工作，如Striped UniFrac和硬件加速的unifrac-binaries，但这些方法均基于原始UniFrac算法，无法从根本上解决扩展性问题。模型估计显示地球可能孕育超过1012种微生物，而现有计算能力远不足以处理如此规模的数据，亟需一种能够扩展至百万样本、数十亿分类单元的算法。
**研究内容与总体结论**
研究人员提出了DartUniFrac算法，首次将UniFrac与加权Jaccard相似度（weighted Jaccard similarity）建立理论联系，并利用草图算法（sketching algorithms）实现快速近似计算。该算法可扩展至数百万个样本和数十亿个分类单元，在CPU和GPU平台上分别比现有最先进算法快200倍以上和约900倍。研究验证了DartUniFrac在多种真实数据集上与原UniFrac计算结果的高度一致性，并展示了其在超大规模微生物组分析中的应用潜力。该成果发表于《Nature Biotechnology》。
**主要关键技术方法**
研究人员使用的主要技术方法包括：一是简洁平衡括号（balanced-parentheses）树表示法，以紧凑位级编码替代指针树结构，支持数十亿分类单元的高效遍历；二是DartMinHash和高效拒绝采样（efficient rejection sampling, ERS）两种加权MinHash草图算法，用于估计加权Jaccard相似度；三是基于GPU的整数汉明相似度加速计算；四是流式处理模式，支持在内存不足时按块计算完整距离矩阵；五是基于随机化奇异值分解（randomized SVD）的快速主坐标分析（fPCoA）。样本队列来源包括EMP、AGP、全球水微生物组联盟（GWMC）、Qiita平台（279,443个扩增子样本）和健康饮食与微生物组倡议（THDMI）等公共数据集。
**研究结果**
*DartUniFrac算法框架与加权Jaccard连接*
研究人员通过数学证明，非加权和加权UniFrac本质上可以转化为系统发育树分支上的加权Jaccard相似度函数。非加权UniFrac距离等于1减去加权Jaccard相似度，而加权UniFrac距离则为(1-Jw)/(1+Jw)。这一理论突破将UniFrac计算问题转化为加权集合的相似度估计问题，从而为使用MinHash类草图算法奠定了基础。
*计算性能基准测试*
性能基准测试表明，DartUniFrac-CPU在样本数从1万到50万范围内，比Striped UniFrac和unifrac-binaries-CPU快200倍以上。在CPU上，DartUniFrac可在1.8小时内完成100万个样本（87,522个分类单元）的两两UniFrac距离计算，而现有最先进算法需要超过20天。DartUniFrac-GPU平均比unifrac-binaries-GPU快约900倍，同时GPU内存消耗降低约24倍。对于100万个以上样本，DartUniFrac-GPU的计算时间比现有算法快1,000倍以上。
*准确性评估*
通过Procrustes分析，DartUniFrac与精确UniFrac在GWMC数据集上的对齐几乎完美（M2=0.0042和0.0039，P<0.001），在EMP数据集上也表现一致。Mantel分析显示，所有数据集的DartUniFrac距离与精确UniFrac距离的相关系数均≥0.98（P<0.001）。草图大小与精度的关系研究表明，随着草图长度增加，均方根误差（RMSE）收敛至0，Mantel相关系数、Procrustes M2、PERMANOVA效应量等指标均趋近于精确结果，证实了算法估计的无偏性。
*可扩展性与流式计算*
分支提取时间随分类单元数量线性增长，但通常仅需数秒，表明平衡括号表示可扩展至数十亿分类单元。DartMinHash草图时间与样本数量成正比，多线程实现下开销较低。流式模式下，GPU运行时间比内存模式慢约2倍，但CPU内存需求降低约10倍。DartUniFrac-GPU仅需约48GB显存即可支持1,000万个样本的默认草图大小计算。该算法还突破了BIOM格式（2.1.0版）包含22?个非零值的限制，在2个GPU上仅需13.8分钟即可完成50万样本、2,000万分类单元的计算。
*下游分析与应用*
研究人员开发了快速主坐标分析（fPCoA）算法，利用随机化SVD替代精确SVD，比精确PCoA快100倍以上，输出结果与精确PCoA几乎一致（Procrustes M2=0.00001）。DartUniFrac还支持大规模重采样统计检验，50轮jackknife重抽样在CPU上45分钟内完成，而精确UniFrac需要10小时以上。此外，DartUniFrac可提供EMDUniFrac的无偏估计，使基于进化关系的差异丰度分析在百万样本规模下成为可能。
**总结讨论与结论**
讨论部分指出，DartUniFrac仅支持非加权和加权UniFrac，但无法计算generalized UniFrac和variance-adjusted UniFrac，因后两者不能表示为树分支上的加权Jaccard相似度。DartUniFrac也可应用于绝对丰度UniFrac，以绝对细胞计数为输入。研究还发现，该算法的瓶颈在于整数汉明相似度计算受内存带宽限制，而非计算密度限制，因此GPU等具有高内存带宽的硬件最为适合。未来可通过增加草图大小进一步提高精度，并支持多节点分布式计算。结论部分总结道：DartUniFrac将使得以精细时空分辨率研究土壤等更多样化环境成为可能，帮助以空前规模解决微生物生态学与进化问题；通过为百万级及以上样本规模提供快速准确的基准真值（ground truth），DartUniFrac也为训练微生物组深度学习模型铺平了道路。
