CIDR: Ultrafast and accurate clustering through imputation for single-cell RNA-seq data.

Lin P, Troup M, Ho JW. · 2017

Read CIDR: Ultrafast and accurate clustering through imputation for single-cell RNA-seq data. by Lin P, Troup M, Ho JW. (2017) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc5371246.txt.

Introduction

Peijie Lin, Michael Troup, and Joshua W. K. Ho built a fast grouping tool for single-cell data in Genome Biology in 2017. Reading genes cell by cell shows how cells differ in kind and state. A flaw dogs the data: many genes drop out of a cell's read, which leaves false zeros that blur the groups. Past fixes leaned on heavy models and slow math.

Their tool, CIDR, fills the gaps in a simple, principled way tucked inside the grouping step itself. With the gaps softened, the standard map method sorts cells far better. On fake and real data sets, CIDR beat the top rival tools on grouping accuracy. It runs in seconds for hundreds of cells and minutes for thousands, on plain gear. The team posts the tool for free download, with notes for users.

Catalog record

CREATORLin P, Troup M, Ho JW.
YEAR2017
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC5371246

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CIDR: Ultrafast and accurate clustering through imputation for single-cell RNA-seq data By Peijie Lin, Michael Troup, Joshua W. K. Ho Published in: Genome Biology DOI: 10.1186/s13059-017-1188-0 ABSTRACT Most existing dimensionality reduction and clustering packages for single-cell RNA-seq (scRNA-seq) data deal with dropouts by heavy modeling and computational machinery. Here, we introduce CIDR (Clustering through Imputation and Dimensionality Reduction), an ultrafast algorithm that uses a novel yet very simple implicit imputation approach to alleviate the impact of dropouts in scRNA-seq data in a principled manner. Using a range of simulated and real data, we show that CIDR improves the standard principal component analysis and outperforms the state-of-the-art methods, namely t-SNE, ZIFA, and RaceID, in terms of clustering accuracy. CIDR typically completes within seconds when processing a data set of hundreds of cells and minutes for a data set of thousands of cells. CIDR can be downloaded at https://github.com/VCCRI/CIDR. Electronic supplementary material The online version of this article (doi:10.1186/s13059-017-1188-0) contains supplementary material, which is available to authorized users. BACKGROUND Single-cell RNA sequencing (scRNA-seq) enables researchers to study heterogeneity between individual cells and define cell types from a transcriptomic perspective. One prominent problem in scRNA-seq data analysis is the prevalence of dropouts, caused by failures in amplification during the reverse-transcription step in the RNA-seq experiment. The prevalence of dropouts manifests as an excess of zeros and near zero counts in the data set, which has been shown to create difficulties in scRNA-seq data analysis [1, 2]. Several packages have recently been developed for the various aspects of scRNA-seq data analysis, including cell cycle (cyclone [3] and scLVM [4]), normalization (scran [5]), differential expression analysis (scde [2] and MAST [6]), and temporal analysis (Monocle [7]), but few perform preprocessing steps such as dimensionality reduction and clustering, which are critical steps for studying cell-type heterogeneity. The state-of-the-art dimensionality-reduction package for scRNA-seq data is ZIFA [1]. It implements a modified probabilistic principal component analysis (PCA) method that incorporates a zero inflated model to account for dropout events. ZIFA uses an iterative expectation-maximization algorithm for inference, which makes it computationally intensive for large scRNA-seq data sets. Another package t-SNE [8] is popular among biologists, but it is not designed specifically for scRNA-seq data and does not address the issue of dropouts. Other recently developed tools, such as BackSPIN [9], pcaReduce [10], SC3 [11], SNN-Cliq [12], RaceID [13], and BISCUIT [14], were designed to deal with optimal clustering of single cells into meaningful groups or hierarchies. Like ZIFA, these algorithms usually involve statistical modeling, which requires estimates of parameters. These algorithms often make use of iterative methods to achieve local or global optimal solutions, and hence they can be slow when processing large data sets of more than several hundred single cells. In many practical situations, researchers are interested in fast and intuitive clustering results that they can easily visualize. PCA is a common analytical approach for data visualization for sample heterogeneity, and is often used for dimensionality reduction prior to clustering. Many versions of PCA, such as the implementation prcomp in R, are very fast and have routinely been used for analyzing large gene expression data sets. Nonetheless, standard PCA is not designed to take into account dropouts in scRNA-seq data. In this work, we aim to develop a fast PCA-like algorithm that takes dropouts into account. RESULTS Motivation We note that PCA is equivalent to performing a principal coordinate analysis (PCoA) on an Euclidean distance matrix derived from the data set. We posit that as long as we can reliably estimate the dissimilarity between every pair of samples (i.e., single cells) in the presence of dropouts, there is no need to estimate explicitly the values of the dropouts. Let us begin by examining the squared Euclidean distance between the expression profiles of two single cells, C i=(o 1i,o 2i,…,o ni) and C j=(o 1j,o 2j,…,o nj), where o ki and o kj represent the gene expression values of gene k in cells C i and C j, respectively: 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$ \begin{aligned} \left[D\left(C_{i},C_{j}\right)\right]^{2}&=\sum_{k=1}^{n}{\left(o_{ki}-o_{kj}\right)^{2}} \\ &=\sum_{k\in\{\text{No zeros}\}}{\left(o_{ki}-o_{kj}\right)^{2}}\\ &\quad+ \sum_{k\in\{\text{Both zeros}\}} {\left(o_{ki}-o_{kj}\right)^{2}}\\ &\quad+ \sum_{k\in\{\text{One zero}\}}{\left(o_{ki}-o_{kj}\right)^{2}}. \end{aligned} $$ \end{document}DCi,Cj2=∑k=1noki−okj2=∑k∈{No zeros}oki−okj2+∑k∈{Both zeros}oki−okj2+∑k∈{One zero}oki−okj2. For simplicity, we refer to all zeros in the gene expression data as dropout candidates. In general, our argument remains valid even when a dropout candidate is allowed to have near zero values. We note that the squared Euclidean distance in Eq. 1 can be arranged as a sum of three sum-of-squares terms. The first term is the sum of squared differences of o ki and o kj if they are both non-zero values. This term is not affected by dropouts. The second term is the sum of squared differences of o ki and o kj if they are both zeros, so this term is zero (or very small, if we include near zero values as dropout candidates). Therefore, we observe that the main impact of dropouts comes from the third term, which deals with when one value is zero and the other is not. A zero can either represent a lack of gene expression in the ground truth or a dropout event in which a non-zero gene expression value is observed as a zero. If we treat all observed zeros as a lack of gene expression (therefore, treating the probability of a zero being a dropout event as zero), which is the case if we directly apply PCA to scRNA-seq data, this term will tend to be inflated. Nonetheless, it has been observed that the probability of a gene expression value being a dropout is inversely correlated with the true expression levels [1, 2]. This means a gene with low expression is more likely to become a dropout than a gene with high expression. Using this information, we hypothesize that we can shrink this dropout-induced inflation by imputing the expression value of a dropout candidate in the third term in Eq. 1 with its expected value given the dropout probability distribution. This is the motivation behind our new method CIDR (Clustering through Imputation and Dimensionality Reduction). The CIDR algorithm The CIDR algorithm can be divided into the following five steps: (1) Identification of dropout candidates, (2) estimation of the relationship between dropout rate and gene expression levels, (3) calculation of dissimilarity between the imputed gene expression profiles for every pair of single cells, (4) PCoA using the CIDR dissimilarity matrix, and (5) clustering using the first few principal coordinates (Additional file 1: Figure S1). CIDR first performs a logarithmic transformation on the tags per million (TPM) gene expression for each cell. The distribution of the log-transformed expression values in a scRNA-seq data set is typically characterized by a strong peak at zero, and one or more smaller non-zero positive peaks representing the expression of expressed genes [6, 15, 16]. For each cell C i, CIDR finds a sample-dependent threshold T i that separates the zero peak from the rest of the expression distribution; Additional file 1: Figure S2a shows the distribution of tags for a library in a simulated data set. The red vertical line indicates the threshold T i. The entries for cell C i with an expression of less than T i are dropout candidates, and

Read the complete text