Multi-Trajectory Pseudotime Inference via Permutation Factorizations

Inferring disease progression from cross-sectional data typically relies on placing individuals along a single latent pseudotemporal axis. However, diseases often exhibit different biomarkers that evolve with different dynamics, making a single shared trajectory insufficient and often leading to biased or inconsistent orderings. We propose a probabilistic framework that maintains a shared global ordering of individuals while allowing clusters of features to follow distinct monotonic trajectories along this ordering. Rather than modeling independent disease progressions, our approach captures heterogeneity through cluster-specific temporal responses defined with respect to a common latent sequence of individuals. The model factorizes inference into a latent permutation over individuals and cluster-specific monotonic functions, enabling flexible yet comparable representations of biomarker dynamics. We jointly infer donor ordering, biomarker clusters, and trajectories within a unified Bayesian framework, using relaxed permutation inference for tractability. Across two major neuropathological datasets in Alzheimers disease, our method recovers biologically meaningful feature clusters and improves alignment with established staging measures compared to single-trajectory baselines. These results show that modeling heterogeneous dynamics relative to a shared progression yields more accurate and interpretable reconstructions of disease progression from cross-sectional data.