Jump to content

User:Slargman/sandbox

From Wikipedia, the free encyclopedia

Trajectory inference (new article)

[edit]
Trajectory inference as implemented in Slingshot for (a) a simulated two-dimensional dataset and (b) a single-cell RNA-seq dataset of the olfactory epithelium.

Trajectory inference (or pseudotemporal ordering) is a comptutational technique used in single-cell transcriptomics to determine the patterns in dynamic processes experienced by the cells and position cells based on their progression through the process. Single-cell protocols have much higher levels of noise than bulk RNA-seq[1], so a common step in a single-cell transcriptomics workflow is the clustering of cells into subgroups.[2] Clustering can contend with this inherent variation by combining the signal from many cells and allows for the identification of cell types.[3] However, some differences in gene expression between cells are the result of dynamic processes such as the cell cycle, cell differentiation, or response to an external stimuli. Trajectory inference seeks to characterize such differences by placing cells along a continuous path that represents the evolution of the process rather than dividing cells into discrete clusters.[4] In some methods this is done by projecting cells onto an axis called pseudotime which represents the progression through the process.[5]

Methods

[edit]

Since 2015, more than 50 algorithms for trajectory inference have been created.[6] Although the approaches taken are diverse there are some commonalities to the methods. Typically, the steps in the algorithm consist of dimensionality reduction to reduce the complexity of the data, trajectory building to determine the structure of the dynamic process, and projection of the data onto the trajectory so that cells are positioned by their evolution through the process and cells with similar expression profiles are situated near each other.[6] Trajectory inference algorithms differ in the specific procedure used for dimensionality reduction, the kinds of structures that can be used to represent the dynamic process, and the prior information that is required or can be provided.[7]

PCA of a multivariate Gaussian distribution. The vectors shown are the first (longer vector) and second principal components, which indicate the directions of maximum variance.

Dimensionality Reduction

[edit]

The data produced by single-cell RNA-seq can consist of thousands of cells each with expression levels recorded across thousands of genes.[8] In order to efficiently process data with such high dimensionality many trajectory inference algorithm employ a dimensionality reduction procedure such as principal component analysis (PCA), independent component analysis (ICA), or t-SNE as their first step.[9] The purpose of this step is to combine many features of the data into a more informative measure of the data.[4] For example, a coordinate resulting from dimensionality reduction could combine expression levels from many genes that are associated with the cell cycle into one value that represents a cell's position in the cell cycle.[9] Such a transformation corresponds to dimensionality reduction in the feature space, but dimensionality reduction can also be applied to the sample space by clustering together groups of similar cells.[1]

Trajectory Building

[edit]
A graph with six vertices. Many trajectory inference algorithms use graphs to build the trajectory.

Many methods represent the structure of the dynamic process via a graph-based approach. In such an approach the vertices of the graph correspond to states in the dynamic process, such as cell types in cell differentiation, and the edges between the nodes correspond to transitions between the states.[6] The creation of the trajectory graph can be accomplished using k-nearest neighbors or minimum spanning tree algorithms.[10] The topology of the trajectory refers to the structure of the graph and different algorithms are limited to creation of graph topologies of a particular type such as linear, branching, or cyclic.[4]

Priors

[edit]

Some methods require or allow for the input of prior information which is used to guide the creation of the trajectory. The use of prior information can lead to more accurate trajectory determination, but poor priors can lead the algorithm astray or bias results towards expectations.[6] Examples of prior information that can be used in trajectory inference are the selection of start cells that are at the beginning of the trajectory, the number of branches in the trajectory, and the number of end states for the trajectory.[11]

Software

[edit]

Monocle

[edit]

Monocle first employs a differential expression test to reduce the number of genes then applies independent component analysis for additional dimensionality reduction. To build the trajectory Monocle computes a minimum spanning tree, then finds the longest connected path in that tree. Cells are projected onto the nearest point to them along that path.[5]

Slingshot

[edit]

Slingshot clusters cells using k-means and then orders these clusters into lineages by the construction of a minimum spanning tree. Projection of cells onto the tree is achieved by determining a cell's pseudotime value which positions the cell in its progress to the trajectory's end state. No prior information is required.[11]

TSCAN

[edit]

TSCAN performs dimensionality reduction using principal component analysis and clusters cells using a mixture model. A minimum spanning tree is calculated using the centers of the clusters and the trajectory is determined as the longest connected path of that tree. TSCAN is an unsupervised algorithm that requires no prior information.[12]

Wanderlust/Wishbone

[edit]

Wanderlust was developed for analysis of mass cytometry data, but has been adapted for single-cell transcriptomics applications. A k-nearest neighbors algorithm is used to construct a graph which connects every cell to the cell closest to it with respect to a metric such as Euclidean distance or cosine distance. Wanderlust requires the input of a starting cell as prior information.[13]

Wishbone is built on Wanderlust and allows for a bifurcation in the graph topology, whereas Wanderlust creates a linear graph. Wishbone combines principal component analysis and diffusion maps to achieve dimensionality reduction then also creates a KNN graph.[14]

Waterfall

[edit]

Waterfall performs dimensionality reduction via principal component analysis and uses a k-means algorithm to find cell clusters. A minimal spanning tree is built between the centers of the clusters. Waterfall is entirely unsupervised, requiring no prior information, and produces linear trajectories.[15]

References

[edit]
  1. ^ a b Bacher, Rhonda; Kendziorski, Christina (2016-04-07). "Design and computational analysis of single-cell RNA-sequencing experiments". Genome Biology. 17 (1): 63. doi:10.1186/s13059-016-0927-y. ISSN 1474-760X. PMC 4823857. PMID 27052890.{{cite journal}}: CS1 maint: PMC format (link) CS1 maint: unflagged free DOI (link)
  2. ^ Hwang, Byungjin; Lee, Ji Hyun; Bang, Duhee. "Single-cell RNA sequencing technologies and bioinformatics pipelines". Experimental & Molecular Medicine. 50 (8). doi:10.1038/s12276-018-0071-8. ISSN 2092-6413.
  3. ^ Stegle, Oliver; Teichmann, Sarah A.; Marioni, John C. (2015-01-28). "Computational and analytical challenges in single-cell transcriptomics". Nature Reviews Genetics. 16 (3): 133–145. doi:10.1038/nrg3833. ISSN 1471-0056.
  4. ^ a b c Cannoodt, Robrecht; Saelens, Wouter; Saeys, Yvan (2016-10-19). "Computational methods for trajectory inference from single-cell transcriptomics". European Journal of Immunology. 46 (11): 2496–2506. doi:10.1002/eji.201646347. ISSN 0014-2980.
  5. ^ a b Trapnell, Cole; Cacchiarelli, Davide; Grimsby, Jonna; Pokharel, Prapti; Li, Shuqiang; Morse, Michael; Lennon, Niall J; Livak, Kenneth J; Mikkelsen, Tarjei S (2014-03-23). "The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells". Nature Biotechnology. 32 (4): 381–386. doi:10.1038/nbt.2859. ISSN 1087-0156.
  6. ^ a b c d Saelens, Wouter; Cannoodt, Robrecht; Todorov, Helena; Saeys, Yvan (2018-03-05). "A comparison of single-cell trajectory inference methods: towards more accurate and robust tools". bioRxiv: 276907. doi:10.1101/276907.
  7. ^ Bang, Duhee; Lee, Ji Hyun; Hwang, Byungjin (2018-08-07). "Single-cell RNA sequencing technologies and bioinformatics pipelines". Experimental & Molecular Medicine. 50 (8): 96. doi:10.1038/s12276-018-0071-8. ISSN 2092-6413.
  8. ^ Conesa, Ana; Madrigal, Pedro; Tarazona, Sonia; Gomez-Cabrero, David; Cervera, Alejandra; McPherson, Andrew; Szcześniak, Michał Wojciech; Gaffney, Daniel J.; Elo, Laura L. (2016-01-26). "A survey of best practices for RNA-seq data analysis". Genome Biology. 17 (1). doi:10.1186/s13059-016-0881-8. ISSN 1474-760X. PMC 4728800. PMID 26813401.{{cite journal}}: CS1 maint: PMC format (link) CS1 maint: unflagged free DOI (link)
  9. ^ a b Yosef, Nir; Regev, Aviv; Wagner, Allon. "Revealing the vectors of cellular identity with single-cell genomics". Nature Biotechnology. 34 (11): 1145–1160. doi:10.1038/nbt.3711. ISSN 1546-1696.
  10. ^ Cahan, Patrick; Tan, Yuqi; Kumar, Pavithra (2017-01-01). "Understanding development and stem cells using single cell-based analyses of gene expression". Development. 144 (1): 17–32. doi:10.1242/dev.133058. ISSN 1477-9129. PMID 28049689.
  11. ^ a b Street, Kelly; Risso, Davide; Fletcher, Russell B.; Das, Diya; Ngai, John; Yosef, Nir; Purdom, Elizabeth; Dudoit, Sandrine (2017-04-19). "Slingshot: Cell lineage and pseudotime inference for single-cell transcriptomics". bioRxiv: 128843. doi:10.1101/128843.
  12. ^ Ji, Zhicheng; Ji, Hongkai (2016-05-13). "TSCAN: Pseudo-time reconstruction and evaluation in single-cell RNA-seq analysis". Nucleic Acids Research. 44 (13): e117–e117. doi:10.1093/nar/gkw430. ISSN 0305-1048.
  13. ^ "Single-Cell Trajectory Detection Uncovers Progression and Regulatory Coordination in Human B Cell Development". Cell. 157 (3): 714–725. 2014-04-24. doi:10.1016/j.cell.2014.04.005. ISSN 0092-8674.
  14. ^ Setty, Manu; Tadmor, Michelle D; Reich-Zeliger, Shlomit; Angel, Omer; Salame, Tomer Meir; Kathail, Pooja; Choi, Kristy; Bendall, Sean; Friedman, Nir (2016-05-02). "Wishbone identifies bifurcating developmental trajectories from single-cell data". Nature Biotechnology. 34 (6): 637–645. doi:10.1038/nbt.3569. ISSN 1087-0156.
  15. ^ "Single-Cell RNA-Seq with Waterfall Reveals Molecular Cascades underlying Adult Neurogenesis". Cell Stem Cell. 17 (3): 360–372. 2015-09-03. doi:10.1016/j.stem.2015.07.013. ISSN 1934-5909.
[edit]

A collection of 50+ trajectory inference methods within a common interface

A table of tools for the analysis of single-cell RNA-seq data