Reconstruction of Single-Cell Trajectories Using Stochastic Tree Search

Jingyi Zhai, Hongkai Ji, Hui Jiang

Research output: Contribution to journalArticlepeer-review


The recent advancement in single-cell RNA sequencing technologies enables the understanding of dynamic cellular processes at the single-cell level. Using trajectory inference methods, pseudotimes can be estimated based on reconstructed single-cell trajectories which can be further used to gain biological knowledge. Existing methods for modeling cell trajectories, such as minimal spanning tree or k-nearest neighbor graph, often lead to locally optimal solutions. In this paper, we propose a penalized likelihood-based framework and introduce a stochastic tree search (STS) algorithm aiming at the global solution in a large and non-convex tree space. Both simulated and real data experiments show that our approach is more accurate and robust than other existing methods in terms of cell ordering and pseudotime estimation.

Original languageEnglish (US)
Article number318
Issue number2
StatePublished - Feb 2023


  • embedding location tree
  • single-cell RNA sequencing data analysis
  • trajectory reconstruction

ASJC Scopus subject areas

  • Genetics(clinical)
  • Genetics


Dive into the research topics of 'Reconstruction of Single-Cell Trajectories Using Stochastic Tree Search'. Together they form a unique fingerprint.

Cite this