Single cells, many algorithms. The goal of this page is to catalog the many algorithms that estimate pseudotimes for cells based on their gene expression levels. This problem is also referred to as single-cell trajectory inference or ordering. Ultimately, it will contain method names, software links, manuscript links, and brief comments on the particular strengths of each method. Initially, it seeks simply to list as many methods as possible. Some related methods not specifically designed for RNA-seq (e.g. mass cytometry) are included as well. The list also includes methods that are specifically designed to take pseudotemporal data as input.

The initial list was created by Anthony Gitter, but pull requests are very welcome. Thank you to the other contributors.

Anthony Gitter. Single-cell RNA-seq pseudotime estimation algorithms. 2018. doi:10.5281/zenodo.1297422 https://github.com/agitter/single-cell-pseudotime

Informally, the pseudotime estimation problem can be stated as:

• Given: single-cell gene expression measurements for a heterogeneous collection of cells that is transitioning from biological state A to state B
• Return: a quantitative value for each cell that represents its progress in the A to B transition

There are many ways to approach this problem, and major algorithmic steps that are common to most (but not all) methods are:

• Reduce the dimension of the dataset
• Find a smooth progression through the low dimensional data, assuming that cells that are nearby one another in the low dimensional space have similar expression levels because they are at similar points in to A to B process

Dimension reduction sometimes relies on knowledge of important marker genes and sometimes uses the full gene expression matrix. The trajectory through the low dimensional space can be identified using graph algorithms (e.g., minimum spanning tree or shortest path), principal curves, or probabilistic models (e.g., Gaussian process).

Bacher and Kendziorski 2016, Trapnell 2015, Tanay and Regev 2017 and Moon et al. 2017 provide a more comprehensive overview of single-cell RNA-seq and the pseudotime estimation problem. Cannoodt et al. 2016 reviews pseudotime inference algorithms. Pablo Cordero's blog post discusses why it is hard to recover the correct dynamics of a system from single-cell data. For more general lists of methods for single-cell RNA-seq see OMICtools, seandavi/awesome-single-cell, and scRNA-tools. The Hemberg lab single-cell RNA-seq course has an overview of five pseudotime algorithms with usage examples.

Some of the distinguishing factors among algorithms include:

• Use of prior knowledge such as capture times (DeLorean) or switch-like marker genes (Ouija)
• Modeling specific types of biological processes such as branching processes in differentiation (multiple methods) or cyclic processes (Oscope)
• Return a single pseudotime or a posterior distribution over pseudotimes for each cell
• Perform additional analyses after inferring pseudotimes such as regulatory network inference or identifying differentially expressed genes over pseudotime

Saelens et al. 2018 performed a comprehensive evaluation of 29 different single-cell trajectory inference methods and discuss the different types of algorithms in more detail. They benchmark both quantitative performance and assess software quality. See their GitHub repository as well. Tian et al. 2018 also include trajectory inference algorithms in their single-cell RNA-seq benchmarking study.

Software: https://bioconductor.org/packages/release/bioc/html/monocle.html

Monocle manuscript: The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells

Census manuscript: Single-cell mRNA quantification and differential analysis with Census

Monocle 2 manuscript: Reversed graph embedding resolves complex single-cell trajectories

Wanderlust software: http://www.c2b2.columbia.edu/danapeerlab/html/wanderlust.html

Wanderlust manuscript: Single-Cell Trajectory Detection Uncovers Progression and Regulatory Coordination in Human B Cell Development

Cycler manuscript: Trajectories of cell-cycle progression from fixed cell populations

Wishbone software: http://www.c2b2.columbia.edu/danapeerlab/html/wishbone.html

Wishbone manuscript: Wishbone identifies bifurcating developmental trajectories from single-cell data

Software: https://github.com/gcyuan/SCUBA

Manuscript: Bifurcation analysis of single-cell gene expression data reveals epigenetic landscape

Software: https://www.biostat.wisc.edu/~kendzior/OSCOPE/

Manuscript: Oscope identifies oscillatory genes in unsynchronized single-cell RNA-seq experiments

destiny software: http://bioconductor.org/packages/release/bioc/html/destiny.html

Diffusion maps manuscripts: Decoding the regulatory network of early blood development from single-cell gene expression measurements and Diffusion maps for high-dimensional single-cell analysis of differentiation data

destiny manuscript: destiny: diffusion maps for large-scale single-cell data in R

Software: https://github.com/JohnReid/DeLorean

Manuscript: Pseudotime estimation: deconfounding single cell time series

Manuscript: Single-Cell RNA-Seq with Waterfall Reveals Molecular Cascades underlying Adult Neurogenesis

Software: https://github.com/kieranrcampbell/embeddr

Manuscript: Laplacian eigenmaps and principal curves for high resolution pseudotemporal ordering of single-cell RNA-seq profiles

GP-LVM software: https://github.com/kieranrcampbell/gpseudotime

GP-LVM manuscript: Bayesian Gaussian Process Latent Variable Models for pseudotime inference in single-cell RNA-seq data

pseudogp software: https://github.com/kieranrcampbell/pseudogp

pseudogp manuscript: Order Under Uncertainty: Robust Differential Expression Analysis Using Probabilistic Models for Pseudotime Inference

Analysis code: https://github.com/Teichlab/spectrum-of-differentiation-supplements

Manuscript: Single-Cell RNA-Sequencing Reveals a Continuous Spectrum of Differentiation in Hematopoietic Cells

Software: https://github.com/jw156605/SLICER

Manuscript: SLICER: inferring branched, nonlinear cellular trajectories from single cell RNA-seq data

Software: https://github.com/zji90/TSCAN

Manuscript: TSCAN: Pseudo-time reconstruction and evaluation in single-cell RNA-seq analysis

Software: https://github.com/hmatsu1226/SCOUP

Manuscript: SCOUP: a probabilistic model based on the Ornstein–Uhlenbeck process to analyze single-cell expression data during differentiation

Software: https://github.com/mzwiessele/topslam

Manuscript: Topslam: Waddington Landscape Recovery for Single Cell Experiments

Software: https://github.com/kieranrcampbell/ouija and http://www.github.com/kieranrcampbell/ouijaflow

Manuscript: A descriptive marker gene approach to single-cell pseudotime inference

Software: https://github.com/kstreet13/slingshot

Extended vignette: https://github.com/drisso/bioc2016singlecell/tree/master/vignettes

Manuscript: Slingshot: Cell lineage and pseudotime inference for single-cell transcriptomics

Workflow manuscript: Bioconductor workflow for single-cell RNA sequencing: Normalization, dimensionality reduction, clustering, and lineage inference

Software: https://github.com/Teichlab/GPfates

Manuscript: Temporal mixture modelling of single-cell RNA-seq data resolves a CD4+ T cell fate bifurcation

Software: https://github.com/dimenwarper/scimitar

Manuscript: Tracing co-regulatory network dynamics in noisy, single-cell transcriptome trajectories

Software: https://github.com/lengning/WaveCrest

Manuscript: Single-cell RNA-seq reveals novel regulators of human embryonic stem cell differentiation to definitive endoderm

Software: https://cran.r-project.org/web/packages/LEAP/index.html

Software: http://bioconductor.org/packages/release/bioc/html/cellTree.html

Manuscript: CellTree: an R/bioconductor package to infer the hierarchical structure of cell populations from single-cell RNA-seq data

Software: http://www.github.com/kieranrcampbell/mfa

Manuscript: Probabilistic modeling of bifurcations in single-cell gene expression data using a Bayesian mixture of factor analyzers

Software: https://github.com/JinmiaoChenLab/Mpath

Manuscript: Mpath maps multi-branching single-cell trajectories revealing progenitor cell progression during development

Software: https://github.com/rcannood/SCORPIUS

Manuscript: SCORPIUS improves trajectory inference and identifies novel modules in dendritic cell development

Software: https://github.com/hmatsu1226/SCODE

Manuscript: SCODE: an efficient regulatory network inference algorithm from single-cell RNA-Seq during differentiation

Software: https://bioconductor.org/packages/release/bioc/html/switchde.html

Manuscript: switchde: inference of switch-like differential expression along single-cell trajectories

Software: https://github.com/pkathail/magic/

Manuscript: MAGIC: A diffusion-based imputation method reveals gene-gene interactions in single-cell RNA-sequencing data

Software: https://github.com/KrishnaswamyLab/PHATE

Manuscript: Visualizing Transitions and Structure for High Dimensional Data Exploration

Manuscript: SOMSC: Self-Organization-Map for High-Dimensional Single-Cell Data of Cellular States and Their Transitions

Software: https://www.andrew.cmu.edu/user/sabrinar/TASIC

Manuscript: TASIC: determining branching models from time series single cell data

Software: https://github.com/macsharma/FORKS

Manuscript: FORKS: Finding Orderings Robustly using K-means and Steiner trees

Software: https://github.com/yjzhang/uncurl_python and https://github.com/mukhes3/UNCURL_release

Manuscript: Scalable preprocessing for sparse scRNA-seq data exploiting prior knowledge

Software: https://github.com/tinglab/reCAT

Manuscript: Reconstructing cell cycle pseudo time-series via single-cell transcriptome data

Software: Bioconductor package and https://github.com/kieranrcampbell/phenopath

Manuscript: Uncovering pseudotemporal trajectories with covariates from single cell and bulk expression data

Software: https://github.com/ManchesterBioinference/BranchedGP

Manuscript: BGP: identifying gene-specific branching dynamics from single-cell data with a branching Gaussian process

Software: https://github.com/cap76/BranchingGPs

Manuscript: Nonparametric Bayesian inference of transcriptional branching and recombination identifies regulators of early human germ cell development

Software: https://github.com/jw156605/MATCHER and https://pypi.python.org/pypi/pymatcher

Manuscript: MATCHER: manifold alignment reveals correspondence between single cell transcriptome and epigenome dynamics

Software: https://github.com/WangShuxiong/SoptSC

Manuscript: Low-rank Similarity Matrix Optimization Identifies Subpopulation Structure and Orders Single Cells in Pseudotime

Manuscript: Assessment of clonal kinetics reveals multiple trajectories of dendritic cell development

Software: https://github.com/AllonKleinLab/PBA

Manuscript: Fundamental limits on dynamic inference from single cell snapshots

Software: https://github.com/theislab/scanpy and https://pypi.python.org/pypi/scanpy

Manuscript: Scanpy for analysis of large-scale single-cell gene expression data

Software: https://github.com/roshan9128/tides

Manuscript: Learning Edge Rewiring in EMT from Single Cell Data

Software: https://pypi.org/project/wot/

Manuscript: Reconstruction of developmental landscapes by optimal-transport analysis of single-cell gene expression sheds light on cellular reprogramming

Software: https://github.com/theislab/pseudodynamics

Manuscript: Beyond pseudotime: Following T-cell maturation in single-cell RNAseq time series

Software: https://github.com/theislab/graph_abstraction

Manuscript: Graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells

Software: https://github.com/magStra/GPseudoRank

Manuscript: GPseudoRank: MCMC for sampling from posterior distributions of pseudo-orderings using Gaussian processes

Software: https://github.com/dgrun/FateID

Manuscript: FateID infers cell fate bias in multipotent progenitors from single-cell RNA-seq data

Manuscript: cycleX: multi-dimensional pseudotime reveals cell cycle and differentiation relationship of dendritic cell progenitors

Software: https://github.com/ManchesterBioinference/GrandPrix

Manuscript: GrandPrix: Scaling up the Bayesian GPLVM for single-cell data

Manuscript: Modeling acute myeloid leukemia in a continuum of differentiation states

Software: https://github.com/phoenixding/scdiff and https://pypi.python.org/pypi/scdiff/

Manuscript: Reconstructing differentiation networks and their regulation from time series single cell expression data

Manuscript: Topographer Reveals Stochastic Dynamics of Cell Fate Decisions from Single-Cell RNA-Seq Data

Manuscript: Quantifying Waddington's epigenetic landscape: a comparison of single-cell potency measures

Manuscript: Machine learning methods to reverse engineer dynamic gene regulatory networks governing cell state transitions

Software: https://github.com/ucasdp/DensityPath

Manuscript: DensityPath: a level-set algorithm to visualize and reconstruct cell developmental trajectories for large-scale single-cell RNAseq data

Software: https://github.com/pinellolab/stream

Manuscript: STREAM: Single-cell Trajectories Reconstruction, Exploration And Mapping of omics data

Website: http://stream.pinellolab.org/

Software: https://github.com/NetLand-NTU/HopLand

Manuscript: HopLand: single-cell pseudotime recovery using continuous Hopfield network-based modeling of Waddington's epigenetic landscape

Manuscript: Dynamic Distribution Decomposition for Single-Cell Snapshot Time Series Identifies Subpopulations and Trajectories during iPSC Reprogramming

Software: https://github.com/jessica1338/CSHMM-for-time-series-scRNA-Seq

Manuscript: Continuous State HMMs for Modeling Time Series Single Cell RNA-Seq Data

Software: https://github.com/dpeerlab/Palantir/

Manuscript: Palantir characterizes cell fate continuities in human hematopoiesis

Software: https://github.com/phoenixding/tbsp

Manuscript: Cell lineage inference from SNP and scRNA-Seq data

Software: https://github.com/architverma1/tGPLVM

Manuscript: A robust nonlinear low-dimensional manifold for single cell RNA-seq data

Manuscript: Chromatin accessibility dynamics of myogenesis at single cell resolution

Manuscript: Comparison of computational methods for imputing single-cell RNA-sequencing data

Software: https://github.com/soedinglab/prosstt

Manuscript: PROSSTT: probabilistic simulation of single-cell RNA-seq data for complex differentiation processes

Software: https://github.com/shenorrLab/cellAlign

Manuscript: Alignment of single-cell trajectories to compare cellular expression dynamics

Software: http://bioconductor.org/packages/release/bioc/html/CONFESS.html

Manuscript: CONFESS: Fluorescence-based single-cell ordering in R

Software: https://www.cell.com/cms/10.1016/j.cels.2018.07.006/attachment/2b57ebff-a502-4819-b8ed-8a87d17a4ae7/mmc4.zip

Manuscript: Aligning Single-Cell Developmental and Reprogramming Trajectories Identifies Molecular Determinants of Myogenic Reprogramming Outcome

Manuscript: Autoencoder and Optimal Transport to Infer Single-Cell Trajectories of Biological Processes