基于整数规划的二叉度受限最小生成树算法用于单细胞轨迹推断

《BMC Bioinformatics》：Degree-restricted minimum spanning trees for binary cell trajectory inference in single-cell RNA-seq data

摘要

单细胞RNA测序（scRNA-seq）通过拟时间轨迹分析，能够从静态快照中重构细胞状态转换过程。尽管现有方法能够推断树状谱系以表征发育层次，但往往会产生多叉或高度分支的模式，难以在生物学上进行解读。为解决这一局限性，我们提出了一种基于整数规划的二叉结构度受限最小生成树（MST）算法，用于细胞轨迹推断，该方法与Waddington的表观遗传景观中关于细胞命运决策的理论更加一致。为方便部署，我们的方法被实现为高度灵活的插件模块，能够无缝集成到现有的基于图和树的轨迹推断流程中。我们展示了将其集成到Slingshot中进行拟时间推断的过程，并评估了所得到的受约束拓扑与CoSpar派生的参考层次结构之间的一致性。在骨髓单核细胞、人类胎儿免疫细胞和小鼠造血数据集上的结果表明，受约束轨迹具有良好的可解释性，并与无约束MST基线方法进行了描述性比较。

源代码可在 https://github.com/iwakitakuma33/degree_restricted_slingshot 获取。