Helmholtz Gemeinschaft


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

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Item Type:Preprint
Title:Graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells
Creators Name:Wolf, F.A. and Hamey, F. and Plass, M. and Solana, J. and Dahlin, J.S. and Gottgens, B. and Rajewsky, N. and Simon, L. and Theis, F.J.
Abstract:Single-cell RNA-seq allows quantification of biological heterogeneity across both discrete cell types and continuous cell differentiation transitions. We present approximate graph abstraction (AGA), an algorithm that reconciles the computational analysis strategies of clustering and trajectory inference by explaining cell-to-cell variation both in terms of discrete and continuous latent variables (https://github.com/theislab/graph_abstraction). This enables to generate cellular maps of differentiation manifolds with complex topologies - efficiently and robustly across different datasets. Approximate graph abstraction quantifies the connectivity of partitions of a neighborhood graph of single cells, thereby generating a much simpler abstracted graph whose nodes label the partitions. Together with a random walk-based distance measure, this generates a topology preserving map of single cells - a partial coordinatization of data useful for exploring and explaining its variation. We use the abstracted graph to assess which subsets of data are better explained by discrete clusters than by a continuous variable, to trace gene expression changes along aggregated single-cell paths through data and to infer abstracted trees that best explain the global topology of data. We demonstrate the power of the method by reconstructing differentiation processes with high numbers of branchings from single-cell gene expression datasets and by identifying biological trajectories from single-cell imaging data using a deep-learning based distance metric. Along with the method, we introduce measures for the connectivity of graph partitions, generalize random-walk based distance measures to disconnected graphs and introduce a path-based measure for topological similarity between graphs. Graph abstraction is computationally efficient and provides speedups of at least 30 times when compared to algorithms for the inference of lineage trees.
Publisher:Cold Spring Harbor Laboratory Press
Article Number:208819
Date:25 October 2017
Official Publication:https://doi.org/10.1101/208819
Related to:
https://edoc.mdc-berlin.de/18120/Final version

Repository Staff Only: item control page


Downloads per month over past year

Open Access
MDC Library