FastPPM

通过树结构双重动态编程

动机：从多个组织样品的大量DNA测序中重建肿瘤的进化史仍然是一个具有挑战性的计算问题，需要同时对肿瘤组织的反卷积及其进化史的推论。最近，系统发育重建方法通过将重建问题分为两个部分，从而取得了重大进展：固定拓扑的回归问题和对树空间的搜索。尽管已经为后一种搜索问题开发了有效的技术，但由于缺乏快速，专业的算法，回归问题仍然是方法设计和实施的瓶颈。结果：在这里，我们介绍了FastPPM，这是一种快速工具，可以通过树结构的双动态编程来解决回归问题。FastPPM支持任意可分离的凸损耗函数，包括ℓ2，分段线性，二项式和β-二元损失，并为现有算法提供了ℓ2和分段线性损失的渐近改进。我们发现，FastPPM的表现优于专业和通用回归算法，获得了50-450×加速度，同时提供了与现有方法一样准确的解决方案。将FASTPPM纳入几种系统发育推理算法中，立即产生高达400倍的速度，仅需要对现有软件的程序代码进行少量更改。最后，FASTPPM可以在模拟数据和结直肠癌的患者衍生的小鼠模型中分析低覆盖量的大量DNA测序数据，从精度和运行时都优于最先进的系统发育推断算法。可用性：FastPPM在C ++中实现，并在github.com/elkebir-group/fastppm.git上作为命令行接口和Python库可用。