Single-cell RNA-seq pseudotime estimation algorithms
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
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.
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, Moon et al. 2017, and Tritschler et al. 2019 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.
Single-cell expression data have also inspired new methods for gene regulatory network reconstruction, as reviewed by Fiers et al. 2018 and Todorov et al. 2018.
Several of these, such as SINGE, treat pseudotime annotations as time points and extend traditional time series network inference algorithms for single-cell data.
BEELINE and SERGIO benchmark many of these specialized network inference methods.
Choosing a method
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. 2019 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 website and GitHub repository as well.
Tian et al. 2018 also include trajectory inference algorithms in their single-cell RNA-seq benchmarking study.
Temporal Reconstruction Algorithm
Manuscript: Reconstructing the temporal ordering of biological samples using microarray data
Monocle / Monocle 2 / Monocle 3/ Census
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
Monocle 3 manuscript: The single-cell transcriptional landscape of mammalian organogenesis
Wanderlust / Cycler / Wishbone
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
Manuscript: Bifurcation analysis of single-cell gene expression data reveals epigenetic landscape
Manuscript: Oscope identifies oscillatory genes in unsynchronized single-cell RNA-seq experiments
Diffusion maps / destiny
destiny software: http://bioconductor.org/packages/release/bioc/html/destiny.html
Diffusion maps manuscript (a): Decoding the regulatory network of early blood development from single-cell gene expression measurements
Diffusion maps manuscript (b): Diffusion maps for high-dimensional single-cell analysis of differentiation data
destiny manuscript: destiny: diffusion maps for large-scale single-cell data in R
Manuscript: Pseudotime estimation: deconfounding single cell time series
Manuscript: Single-Cell RNA-Seq with Waterfall Reveals Molecular Cascades underlying Adult Neurogenesis
Manuscript: Laplacian eigenmaps and principal curves for high resolution pseudotemporal ordering of single-cell RNA-seq profiles
GP-LVM and pseudogp
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
Manuscript: SLICER: inferring branched, nonlinear cellular trajectories from single cell RNA-seq data
Manuscript: TSCAN: Pseudo-time reconstruction and evaluation in single-cell RNA-seq analysis
Manuscript: SCOUP: a probabilistic model based on the Ornstein–Uhlenbeck process to analyze single-cell expression data during differentiation
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
Manuscript: Transcriptional dynamics of hair-bundle morphogenesis revealed with CellTrails
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
Manuscript: Temporal mixture modelling of single-cell RNA-seq data resolves a CD4+ T cell fate bifurcation
Manuscript: Tracing co-regulatory network dynamics in noisy, single-cell transcriptome trajectories
Manuscript: Single-cell RNA-seq reveals novel regulators of human embryonic stem cell differentiation to definitive endoderm
Manuscript: CellTree: an R/bioconductor package to infer the hierarchical structure of cell populations from single-cell RNA-seq data
Bayesian hierarchical mixture of factor analysers (MFA)
Manuscript: Probabilistic modeling of bifurcations in single-cell gene expression data using a Bayesian mixture of factor analyzers
Manuscript: Mpath maps multi-branching single-cell trajectories revealing progenitor cell progression during development
Manuscript: SCORPIUS improves trajectory inference and identifies novel modules in dendritic cell development
Manuscript: SCODE: an efficient regulatory network inference algorithm from single-cell RNA-Seq during differentiation
Manuscript: switchde: inference of switch-like differential expression along single-cell trajectories
Manuscript: MAGIC: A diffusion-based imputation method reveals gene-gene interactions in single-cell RNA-sequencing data
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
Manuscript: TASIC: determining branching models from time series single cell data
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
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
Branched Gaussian processes
Manuscript: BGP: identifying gene-specific branching dynamics from single-cell data with a branching Gaussian process
Branch-recombinant Gaussian Processes
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
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
Population Balance Analysis
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
Manuscript: Learning Edge Rewiring in EMT from Single Cell Data
Manuscript: Reconstruction of developmental landscapes by optimal-transport analysis of single-cell gene expression sheds light on cellular reprogramming
Manuscript: Inferring population dynamics from single-cell RNA-sequencing time series data
Partition-based graph abstraction
Manuscript: PAGA: graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells
Manuscript: GPseudoRank: MCMC for sampling from posterior distributions of pseudo-orderings using Gaussian processes
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
Manuscript: GrandPrix: Scaling up the Bayesian GPLVM for single-cell data
Partial differential equations
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
Manuscript: DensityPath: a level-set algorithm to visualize and reconstruct cell developmental trajectories for large-scale single-cell RNAseq data
Manuscript: STREAM: Single-cell Trajectories Reconstruction, Exploration And Mapping of omics data
Manuscript: HopLand: single-cell pseudotime recovery using continuous Hopfield network-based modeling of Waddington's epigenetic landscape
Dynamic Distribution Decomposition
Manuscript: Dynamic Distribution Decomposition for Single-Cell Snapshot Time Series Identifies Subpopulations and Trajectories during iPSC Reprogramming
Continuous state HMMs
Manuscript: Continuous State HMMs for Modeling Time Series Single Cell RNA-Seq Data
Manuscript: Palantir characterizes cell fate continuities in human hematopoiesis
Trajectory inference Based on SNP information
Manuscript: Cell lineage inference from SNP and scRNA-Seq data
t-Distributed Gaussian Process Latent Variable Model
Manuscript: A robust nonlinear low-dimensional manifold for single cell RNA-seq data
Manuscript: Systematic Reconstruction of Molecular Cascades Regulating GP Development Using Single-Cell RNA-Seq
Lineage tracing on transcriptional landscapes
Software: Multiple repositories
Manuscript: Lineage tracing on transcriptional landscapes links state to fate during differentiation
Manuscript: CALISTA: Clustering And Lineage Inference in Single-Cell Transcriptional Analysis
Manuscript: Mapping Lung Cancer Epithelial-Mesenchymal Transition States and Trajectories with Single-Cell Resolution
Manuscript: psupertime: supervised pseudotime inference for single cell RNA-seq data with sequential labels
Manuscript: OscoNet: Inferring oscillatory gene networks
Manuscript: Latent periodic process inference from single-cell RNA-seq data
Manuscript: Reconstructing complex lineage trees from scRNA-seq data using MERLoT
Manuscript: Generalizing RNA velocity to transient cell states through dynamical modeling
Manuscript: Tempora: cell trajectory inference using time-series single-cell RNA sequencing data
Manuscript: CellCycleTRACER accounts for cell cycle and volume in mass cytometry data
Manuscript: TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics
Manuscript: redPATH: Reconstructing the Pseudo Development Time of Cell Lineages in Single-Cell RNA-Seq Data and Applications in Cancer
GraphDR and StructDR
Manuscript: An analytical framework for interpretable and generalizable 'quasilinear' single-cell data analysis
Manuscript: Inferring cellular trajectories from scRNA-seq using Pseudocell Tracer
Manuscript: Chromatin accessibility dynamics of myogenesis at single cell resolution
Effects of imputation on cell ordering
Manuscript: Comparison of computational methods for imputing single-cell RNA-sequencing data
Manuscript: PROSSTT: probabilistic simulation of single-cell RNA-seq data for complex differentiation processes
Manuscript: Alignment of single-cell trajectories to compare cellular expression dynamics
Manuscript: CONFESS: Fluorescence-based single-cell ordering in R
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
Manuscript: RNA velocity of single cells
Manuscript: High Resolution Comparison of Cancer-Related Developmental Processes Using Trajectory Alignment
Manuscript: Dynamic pseudo-time warping of complex single-cell trajectories
Manuscript: Network Inference with Granger Causality Ensembles on Single-Cell Transcriptomic Data
Manuscript: GPseudoClust: deconvolution of shared pseudo-trajectories at single-cell resolution
Manuscript: Trajectory-based differential expression analysis for single-cell sequencing data
Manuscript: A gene filter for comparative analysis of single-cell RNA-sequencing trajectory datasets
Manuscript: Benchmarking algorithms for gene regulatory network inference from single-cell transcriptomic data
Manuscript: Mapping Vector Field of Single Cells
Manuscript: A single-cell expression simulator guided by gene regulatory networks
Manuscript: GeneSwitches : Ordering gene-expression and functional events in single-cell experiments
Manuscript: Alignment of time-course single-cell RNA-seq data with CAPITAL
Transcriptional uncertainty landscapes
Manuscript: Universality of cell differentiation trajectories revealed by a reconstruction of transcriptional uncertainty landscapes from single-cell transcriptomic data
Manuscript: Pseudo-Location: A novel predictor for predicting pseudo-temporal gene expression patterns using spatial functional regression
Software: http://bioconductor.org/packages/devel/bioc/html/fishpond.html and https://github.com/skvanburen/scUncertaintyPaperCode
Manuscript: Compression of quantification uncertainty for scRNA-seq counts
Manuscript: Investigating higher-order interactions in single-cell data with scHOT