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
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
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
Software: https://cran.r-project.org/web/packages/LEAP/index.html
Software: http://bioconductor.org/packages/release/bioc/html/cellTree.html
Software: http://www.github.com/kieranrcampbell/mfa
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
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: 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/
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
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
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
Software: https://github.com/ucasdp/DensityPath
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
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
Manuscript: Autoencoder and Optimal Transport to Infer Single-Cell Trajectories of Biological Processes