参考链接：（轨迹分析的算法原理）单细胞系列课程-10 Trajectory inference analysis of scRNA-seq data - 简书 (jianshu.com)
monocle1
涉及的算法：MST（minimum spamming tree）-最小生成树
举个例子：下图中有很多点，每个点之间的距离都可以计算（比如使用DM来计算点和点之间的possibility）。将点连线，寻找一个所有的点之间距离加和最小的连接方式，得到的结果如黑色的粗线所示，这就是最小生成树。细胞数目越多，MST的轨迹构建越准确。
monocle1中使用的就是这种方式。如下图a：每个细胞都代表了高维空间中的一个点，将高维空间降维（使用PCA/ICA或UMAP/TSNE），随后使用MST定义细胞轨迹，并将细胞按照MST构建的生成树排序，标注上细胞类型，就可以得到细胞轨迹。
但值得注意的是，MST只能构建细胞轨迹，但不能告诉你端点是转录起始点还是终止点，也就是不知道是从哪个方向向哪个方向分化。所以如果有先验知识（比如干细胞向别的细胞分化），就会容易很多。
此外，由于MST没有循环，所以不适用于增殖细胞（细胞周期）样本。
monocle2
涉及的算法：RGE(Reverse graph embedding, i.e. DDRTree and others)-反向图嵌入
如下图A和B：在使用MST进行轨迹推断时，由于最小生成树高度依赖于每个点的位置和点与点之间的距离，仅仅只是某个点的位置有些微变化就会得到完全不同的细胞轨迹。而REG的方法（图C）则是先对细胞进行聚类，再对细胞群的平均值进行轨迹构建。
Monocle2中使用的就是RGE方法(DDRTree)。
reversed graph embedding能够同时获得反映数据隐藏结构的曲线并同时得到所有点在曲线上的映射。它既能保证最终获得收敛的结果，同时也适用于对大的数据集进行分析。
上图显示的是RGE的工作原理。每个细胞都代表了高维空间中的一个点，使用PCA或其他方法来对细胞进行降维后，根据假定的细胞cluster的中心点来对轨迹进行构建。随后计算细胞到假设轨迹的距离，并将细胞分配到距离细胞最近的轨迹cluster上，分配完成后对中心点进行更新，重建轨迹，再将二维轨迹投射到多维空间里，比较与原始数据的契合度，如果match的不好，就重新降维和构建轨迹，循环这个过程，直到细胞轨迹能充分反映原始data（类似降维中的TSNE和UMAP循环）。这时就可以选择轨迹的root（需要先验知识），并对拟时间轴或者发育轨迹进行定义。根据轨迹图中的分叉，还可以定义cell fate。
REG还衍生出了许多方法，比如PAGA、Slingshot、TSCAN、CellRouter等。
monocle3
Monocle3和Monocle2并没有本质上的区别，只是把降维图从DDRTree改成了UMAP。另外，相较于Monocle2，Monocle3通过选择并只处理具有代表性的细胞（landmark cells）来应对更大的数据量。同时，它舍弃了较小的分化分支（branch），只保留主要的trajectory结构。它还提供了更为灵活的trajectory结构而不只局限于树状结构，以描绘细胞中更为复杂的分化情况。
Monocle3的工作流程：scRNAseq数据 --> 预处理（标准化+PCA）--> 降维 --> 聚类 --> 拟时间轴的建立（DDRTree、SimplePPT、L1-graph）--> 差异分析
重要的更新:
1)支持UMAP算法初始化轨迹推理
2）支持多跟轨迹
3）学习具有循环或收敛点的轨迹的方法
4）使用“近似图抽象”的思想自动划分单元以学习不相交或平行轨迹的算法。
5）对具有轨迹依赖性表达的基因进行新的统计检验。这将替换旧的differentialGene Test()函数和BEAM（）函数。
6）3D界面，可视化轨迹和基因表达。
slingshot
官方教程：Slingshot: Trajectory Inference for Single-Cell Data (bioconductor.org)
软件文献：Slingshot: cell lineage and pseudotime inference for single-cell transcriptomics | BMC Genomics | Full Text (biomedcentral.com)
slingshot包可以对单细胞RNA-seq数据进行细胞分化谱系构建和伪时间推断。它利用细胞聚类簇和空间降维信息，以无监督或半监督的方式学习细胞聚类群之间的关系，揭示细胞聚类簇之间的全局结构，并将该结构转换为由一维变量表示的平滑谱系，称之为“伪时间”。
1）谱系的识别，即细胞簇的有序集合，其中所有谱系共享一个起始簇，每个谱系通向一个独特的末端簇。这是通过在细胞簇上构建最小生成树（MST）来实现的，最终确定谱系的数量和粗略形状。
2）使用同步主曲线（simultaneous principal curves）来获得每个谱系的平滑表示（即将平滑分支曲线拟合到这些谱系）。
3）通过将细胞正交投影到曲线上获得伪时间值（仅针对面板（a）显示）
