Modern single-cell technologies allow multiplexed sampling of cellular states within a tissue. However, computational tools that can infer developmental cell-state transitions reproducibly from such single-cell data are lacking. Here, we introduce p-Creode, an unsupervised algorithm that produces multi-branching graphs from single-cell data, compares graphs with differing topologies, and infers a statistically robust hierarchy of cell-state transitions that define developmental trajectories. We have applied p-Creode to mass cytometry, multiplex immunofluorescence, and single-cell RNA-seq data. As a test case, we validate cell-state-transition trajectories predicted by p-Creode for intestinal tuft cells, a rare, chemosensory cell type. We clarify that tuft cells are specified outside of the Atoh1-dependent secretory lineage in the small intestine. However, p-Creode also predicts, and we confirm, that tuft cells arise from an alternative, Atoh1-driven developmental program in the colon. These studies introduce p-Creode as a reliable method for analyzing large datasets that depict branching transition trajectories.

Unsupervised Trajectory Analysis of Single-Cell RNA-Seq and Imaging Data Reveals Alternative Tuft Cell Origins in the Gut