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 monotone trajectories along this ordering. Rather than assigning individuals to separate progressions, our approach captures heterogeneity through cluster-specific temporal responses defined with respect to a common latent sequence of individuals. Our key observation is that monotone transformations of a common progression preserve the ordering of individuals, so multiple pseudotimes factorize into a single 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 stochastic variational inference over permutations. Across two major neuropathological datasets in Alzheimer's disease, our method recovers biologically meaningful feature clusters and improves overall 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.