Degree-restricted minimum spanning trees for binary cell trajectory inference in single-cell RNA-seq data

Single-cell RNA sequencing (scRNA-seq) enables the reconstruction of cell state transitions from static snapshots through pseudotime trajectory analysis. Although existing methods can infer tree-structured lineages to characterize developmental hierarchies, they often generate multifurcating or high-degree branching patterns that are difficult to interpret biologically. To address this limitation, we propose an integer programming based degree-restricted minimum spanning tree (MST) algorithm for binary-structured cell trajectory inference, which aligns more closely with Waddington’s epigenetic landscape for cell fate decisions. To facilitate deployment, our method is implemented as a highly flexible plug-in module that can be seamlessly integrated into existing graph- and tree-based trajectory inference pipelines. We demonstrate its integration into Slingshot for pseudotime inference and evaluate the consistency of the resulting constrained topology against a CoSpar-derived reference hierarchy. Results on bone marrow mononuclear cell, human fetal immune cell, and mouse hematopoiesis datasets illustrate the interpretability of the constrained trajectories and provide a descriptive comparison with unconstrained MST baselines. The source code is available at https://github.com/iwakitakuma33/degree_restricted_slingshot .