Dolphyin：一种用于识别癌症中一维Dollo系统发育树的组合算法

《Algorithms for Molecular Biology》：Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer

　　

摘要

背景

最近的一些癌症系统发育推断方法采用了 k-Dollo 进化模型来处理单核苷酸变异，该模型要求在二进制测序数据矩阵 B 上构建一个系统发育树 T，使得每个变异最多出现 k 次并最多丢失 k 次。1-Dollo 变异已经得到了广泛研究，但其复杂性问题仍未解决。

结果

我们证明了 1-Dollo 线性系统发育（1DLP）问题（其中我们还要求得到的 1-Dollo 系统发育树 T 是线性的）等价于验证矩阵 B 是否具有“连续 1”的性质，而这一性质可以在多项式时间内确定。我们还表明，1DLP 的一些实际扩展（例如最小化假阴性结果）属于 NP 难问题。接着，我们展示了如何将任何 1-Dollo 系统发育树 T（不一定是线性的）递归分解为多个 1-Dollo 线性系统发育树，并将这种特性推广到所有允许存在 1-Dollo 系统发育树的矩阵 B。我们利用这一特性开发了 Dolphyin，这是一种新的指数时间算法，用于推断 1-Dollo 系统发育树。在模拟数据集上，Dolphyin 的运行时间与基于整数线性规划的算法 SPhyR（El-Kebir 2018）相当，并且能够推断出假阴性测序错误率在模拟真实错误率及以下的 1-Dollo 系统发育树。我们将 Dolphyin 应用于急性髓系白血病数据集，发现大多数癌症可以通过符合所用测序技术的 1-Dollo 系统发育树来解释。

结论

我们的工作开发了一种新颖的组合算法，用于实际推断 1-Dollo 系统发育树。

背景

最近的一些癌症系统发育推断方法采用了 k-Dollo 进化模型来处理单核苷酸变异，该模型要求在二进制测序数据矩阵 B 上构建一个系统发育树 T，使得每个变异最多出现 k 次并最多丢失 k 次。1-Dollo 变异已经得到了广泛研究，但其复杂性问题仍未解决。

结果

我们证明了 结论

我们的工作开发了一种新颖的组合算法，用于实际推断 1-Dollo 系统发育树。