利用有向无环图系统搜索，探寻高后验密度系统发育树

研究人员针对贝叶斯系统发育学计算难题，开展基于子分裂有向无环图（sDAG）的研究，发现聚合 sDAG 策略更优。

　　在生物学的进化研究领域，系统发育树就像是一部记录物种演化历程的 “生命史书”，它能帮助我们了解不同物种之间的亲缘关系和演化轨迹。而贝叶斯系统发育学，作为构建和分析这部 “生命史书” 的重要手段，却面临着巨大的挑战。

现有的贝叶斯系统发育学方法大多基于马尔可夫链蒙特卡罗（MCMC）算法。想象一下，MCMC 算法就像是在一个巨大的迷宫里随机游走寻找出口，这个迷宫就是系统发育树的拓扑结构空间。由于高可信度的拓扑结构区域只是这个超指数级大小空间的一个微小部分，所以大部分随机修改得到的 “树” 都不太理想，就像在迷宫里大部分尝试都走向了死胡同，这导致了极低的接受率，大大降低了计算效率。而最大似然法虽然能系统地寻找最大似然树，但它却无法全面地描述所有可能的树或拓扑结构的可信集。

为了解决这些问题，来自弗雷德?哈钦森癌症研究中心（Fred Hutchinson Cancer Research Center）、澳大利亚悉尼科技大学等多个机构的研究人员，包括 Chris Jennings-Shaffer、David H. Rich 等，开展了一项关于利用子分裂有向无环图（sDAG）来系统搜索高后验密度系统发育树的研究。该研究成果发表在《Algorithms for Molecular Biology》上。

研究人员用到的主要关键技术方法有：首先是引入 sDAG，它是一种能够同时存储和处理多种树或拓扑结构的计算结构，通过对 sDAG 进行操作来避免单独考虑过多拓扑结构的问题；其次是将最近邻互换（NNI）操作扩展到 sDAG 上，通过 NNI 操作来扩大 sDAG；然后使用两种评估方法，即 “顶修剪（top pruning）” 和 “广义修剪（generalized pruning，GP）”，来决定是否对 sDAG 应用 NNI 操作。

研究结果如下：

1. 广义修剪的表现：广义修剪在所有数据集上的表现都不尽人意，它无法在合理时间内捕获足够的后验密度，在添加子分裂和边时，很多都对提高密度没有贡献，与短时间运行 MrBayes 得到的拓扑结构列表相比，没有竞争力。
2. 顶修剪的表现：顶修剪在 DS 数据集上的表现优于广义修剪，它的表现优于短时间的 MCMC 运行结果，并且与由这些短时间运行结果生成的 sDAG 具有竞争力。不过，顶修剪找到的子分裂的可信度往往比短时间运行 MrBayes 得到的结果要差，会添加许多不可信的子分裂。
3. 不同起始树的影响：使用多个起始树对顶修剪是有益的，但具体效果取决于起始树的选择。使用 10 个最高概率的树作为起始树，提升效果不明显；而使用 RAxML 生成的高似然树作为起始树，通常能在搜索初期更好地选择 NNI 操作，提高搜索效率。
4. 运行时间分析：顶修剪的运行时间并非与迭代次数呈线性关系，随着迭代进行，计算量会增加，但最差情况下是二次方关系。在流感数据集上的表现与 DS 数据集一致，这表明顶修剪在处理更多分类单元（taxa）时可能具有较好的扩展性。
5. 边缘后验概率与似然性比较：通过比较边缘的后验概率和顶修剪似然性，发现高后验概率与高似然性有较好的对应关系，这说明顶修剪算法在对可信集内的边缘进行排序方面表现尚可，但存在找到并包含可信集外边缘的问题。

研究结论和讨论部分指出，该研究开发了识别树空间中潜在高后验密度区域的策略，这是通过优化推断贝叶斯系统发育后验分布这一更大计划的一部分。虽然顶修剪在测试数据集上表现出一定的合理性，但目前测试数据集中序列数量相对较小，还不清楚其在更大数据集上的表现。而且，聚合 MCMC 采样树到 sDAG 的策略在小数据集上的表现优于顶修剪，这为未来的研究和基准测试提供了更有前景的方向。广义修剪虽然在确定分支长度方面有一定作用，但在 NNI 搜索中表现不佳，可能是其对新引入拓扑结构质量的评估不够充分。此外，研究人员还提出了一些可能的扩展方向，如尝试更多不同的边缘添加方式，以及对相关算法进行改进等。这项研究为贝叶斯系统发育学的发展提供了新的思路和方法，尽管目前还存在一些问题，但为后续研究奠定了基础，有助于推动该领域进一步发展。