henhao
Sign in
BioinformaticsbioRxiv
Preprint

sfate: Schur-free, target-conditioned absorption probabilities for scalable single-cell fate analysis

Wei ZengiD, Lei Shi

Abstract

Motivation: Single-cell fate mapping at atlas scale is constrained by memory: in the tested CellRank 2.3.2 pip environment without the optional PETSc/SLEPc stack, the GPCCA estimator fell back--after a warning--to a dense Brandts Schur routine. Across three measured sizes, its peak memory was consistent with ~72 n^2 bytes, a model that back-calculates to ~405 GB [BACK-CALCULATED] for the 74,984-cell dataset studied here--beyond any consumer workstation. Results: We present scalable-fate (sfate), which computes absorption probabilities to annotation-defined target states--where 'fate probability' denotes absorption probability toward user-defined target states on a latent-space transition graph, conceptually related to Palantir-style diffusion-based Markov-chain fate modeling rather than a velocity-derived lineage probability--from latent-space kNN graphs via column-wise GMRES solves, without any Schur decomposition. Memory scaled linearly with cell number over four measured graph-construction tiers (R^2 = 0.9985; 4.03 GiB at 500,000 synthetic cells in 66.2 s); the 500k absorption solve did not converge under the default configuration, so the largest measured full-pipeline scale is the 75k real-data run (1.76 GiB). Solutions agree with float64 direct references within the prespecified 1e-5 tolerance at every tested configuration (production default L-inf = 1.74e-06; best tested configuration 3.21e-07, 31x below the threshold), and reproduce CellRank's fate probabilities when the transition kernel and terminal representative cells are held identical. On 75k mouse 5xFAD/Cd28-cKO microglia (Ayata et al., 2025; GEO: GSE296768), the full analysis ran at 1.76 GiB peak memory, returning a six-state annotation-defined absorption landscape where the archived CellRank analysis returned three comparable arms; a controlled 2x2 comparison identifies terminal-state selection as an important contributor to the cross-tool discrepancy. Availability: sfate is available at https://github.com/Ericleo-zeng/sfate (release v1.0.0, commit 5472f62; MIT license) and is archived at Zenodo (DOI: 10.5281/zenodo.22851715). The repository includes the source code, the validation suite (32 unit tests, deterministic under fixed seed), all benchmark and figure-generation scripts, the synthetic fixtures, and the records underlying every figure and table. Contact: Wei Zeng (ericleo_zeng@hotmail.com)

PDFDOICode
Full-text digest ↓

02 /Specification & Classification

Click any tag to browse matching papers
Citations
0
OpenAlex Topics

In-depth summary

✦ Multi-agent verified full-text synthesis

Claude Opus 5.5 · xhigh effort · 8 Nov 2026 · from the full text of version 1 (25 Sept 2026) · CC BY 4.0

sfate computes annotation-targeted absorption probabilities by column-wise GMRES on a latent kNN graph, skipping Schur decomposition; a 74,984-cell mouse microglia analysis peaked at 1.76 GiB.

Without the optional PETSc/SLEPc stack, CellRank's GPCCA estimator falls back to a dense Brandts Schur routine whose measured memory fits about 72·n² bytes, back-calculated to about 405 GB for 75k cells. CellRank already supports explicit targets and iterative absorption solves; sfate instead makes the target-conditioned solve the whole pipeline, dropping the Schur, macrostate and curation stages for pure scipy, linear memory and an explicit numerical validation protocol.

Key results

  1. ShownThe quadratic memory wall comes from CellRank's dense Brandts Schur fallback, which runs when PETSc/SLEPc is missing, and not from GPCCA itself. With the krylov-Schur path installed, the full GPCCA pipeline ran at 500k cells in a few GiB.

    Brandts peak memory was 268 MiB (n=2,000), 1.68 GiB (5,000) and 4.29 GiB (8,000), fitting about 72 B per cell²; the run hit OOM at n=10,000 in a 4 GB sandbox; back-calculated need about 405 GB at 74,984 cells. Krylov-Schur (petsc4py 3.25.5/slepc4py 3.25.1, cellrank 2.1.0) on synthetic data: 1.53 GiB peak in 2 min 3 s at 100k; 3.67 GiB in 7 min 31 s at 500k. · Results 1 — The quadratic memory wall of the…

  2. Shownsfate's graph-construction memory grew linearly with cell number up to 500k synthetic cells. At that size it was comparable to (not below) krylov-Schur CellRank. The 500k absorption solve did not converge, so 75k is the largest complete run.

    Peak RSS was 0.71 GiB (5k real), 0.80 GiB (10k synthetic), 1.32 GiB (75k real) and 4.03 GiB (500k synthetic, 66.2 s). Linear fit: 740 + 6.60 MiB per 1,000 cells, R² = 0.9985. At 500k, GMRES for the first absorbing cell stopped at 49,904 iterations with a true residual of 1.09e-5 (rtol 1e-6). Krylov-Schur CellRank used 3.67 GiB at 500k. · Results 2 — sfate: a Schur-free, linear-memory…; Benchmarking protocol

  3. ShownOn a 5k real-data fixture, sfate's float32 GMRES solutions matched float64 direct solves within the prespecified 1e-5 tolerance. Given CellRank's own kernel and terminal cells, sfate reproduced CellRank's fate probabilities.

    Layer A, 2×2 grid (solve mode × preconditioner): L∞ from 2.34e-07 to 1.74e-06 against scipy spsolve (production default 1.74e-06; ILU aggregated 3.21e-07), with 26 to 30 GMRES iterations per class and zero float64 fallbacks. Layer B against CellRank: L∞ = 1.07e-06. The direct float64 solve took 37.7 s per class versus 0.73 s for GMRES. · Results 3 — Numerical validation: agreement with…; Validation protocol

  4. SuggestedIn a controlled 5k kernel × terminal-set comparison, swapping the terminal-state set changed fate landscapes more than swapping the kernel. CellRank's automatic count of terminal states depended on the stability threshold.

    Minimum per-class Spearman was 0.136 (range 0.136 to 0.640) for the terminal-set contrast versus 0.830 (0.830 to 0.940) for the kernel contrast. Fully automatic GPCCA at 5k gave one terminal state; thresholds 0.90/0.93/0.96/0.99 gave 3/2/1/0. At 75k the archived run split IFN_responsive into three substates and marked DAM_like and PU1low_lymphoid as unsupported. · Results 4 — Spectral terminal-state curation and…

  5. ShownOn 74,984 mouse 5xFAD/Cd28-cKO microglia, sfate gave absorption probabilities toward all six annotated states at about 1.76 GiB peak; the archived CellRank run covered three comparable arms. Sample-level directional agreement between the two was not significant.

    Column-wise six-state solve: 29.0 s, about 59 GMRES iterations per column, maximum true residual 1.9e-7. The aggregated right-hand-side + ILU(1) setup took 3,915 s, with 5 of 6 classes missing rtol 1e-6 within 50,000 iterations. Genotype-delta signs agreed in 9/15 comparison cells (sign-permutation p_all = 0.339). Per-cell Spearman: Homeostatic −0.568, IFN_responsive 0.320. · Results 5 — Real-data case: a 75k Alzheimer’s…; Data

Methods, data and reproducibility

sfate builds a pynndescent kNN graph (k=30) on a 30-d scVI latent, makes it a Gaussian-weighted row-stochastic float32 matrix, sets the 30 centroid-nearest cells per annotated class as absorbing, and solves (I−Q)X = R column-wise by unpreconditioned GMRES. Memory was compared with CellRank's Brandts and krylov-Schur paths; accuracy with float64 direct and CellRank solutions.

  • Processed atlas of forebrain microglia from the 5xFAD/Cd28-cKO study of Ayata et al.: 12 samples, three genotypes, ages 3, 6 and 8 months; 30-d scVI latent and six-state annotation used · mouse · n = 74,984 cells; 12 samples · GEO: GSE296768
  • Real-data validation fixture carrying the six annotated microglia states (Layers A/B and the sensitivity analyses); distributed with the code package · n = 5,000 cells · Zenodo DOI: 10.5281/zenodo.22851715
  • Synthetic fixtures and branching topologies for the sfate scaling tiers and the krylov-Schur CellRank benchmarks · none (synthetic) · n = 10,000; 100,000; 500,000 cells
  • Synthetic orphan-free chain for the strict backward-error unit test (a2) · none (synthetic) · n = 1,600
  • Archived CellRank 'step12' fate outputs on the same atlas, used as a historical reference (three comparable fate arms) · mouse
Methods & tools
sfate, CellRank 2.1.0 / 2.3.2, pyGPCCA 1.0.4, PETSc/SLEPc (petsc4py 3.25.5, slepc4py 3.25.1), scVI, pynndescent 0.6.0 (NN-Descent), scikit-learn, SciPy 1.15.3 (gmres, spsolve, spilu), h5py 3.16.0, anndata 0.12.16, scanpy 1.11.5, statsmodels (mixedlm)
Code
https://github.com/Ericleo-zeng/sfate
Software & environment
Python 3.12.9; cellrank 2.1.0 (Brandts n² model fitted on 2.3.2); pygpcca 1.0.4; scanpy 1.11.5; anndata 0.12.16; scipy 1.15.3; numpy 2.4.2; h5py 3.16.0; pynndescent 0.6.0; petsc4py 3.25.5/slepc4py 3.25.1 for krylov control; sfate v1.0.0, commit 5472f62, MIT; 32 unit tests
Assay conditions & compute
Consumer workstation: AMD Ryzen 9 8945HX (16 cores/32 threads), 32 GB RAM (30 GiB visible), Ubuntu 24.04.4, NVMe SSD; single process, BLAS threads = 1. The 75k full run peaked at 1.76 GiB (six-state solve 29.0 s); 500k graph construction took 66.2 s at 4.03 GiB.
Reproducibility gaps
Raw data are in GEO GSE296768; the 5k fixture and 75k fate matrices are in the Zenodo archive (10.5281/zenodo.22851715). The processed h5ad is on institutional storage, and its manifest to GSE296768 is only promised. No link is given for the scVI latent and annotations.
Limitations (6)
  • At 500k cells only graph construction succeeded. The default GMRES did not converge for the first absorbing cell (49,904 iterations, true residual 1.09e-5), so the 1M memory extrapolation covers graph and I/O only. Accuracy of the approximate graph at 500k was not evaluated. · stated by the authors
  • The 135× speed difference at 75k mixes two changes, right-hand-side organization and ILU preconditioning. A factorial comparison is needed before either factor can be credited. · stated by the authors
  • The fate landscape depends on the embedding: replacing the scVI latent with a 30-dimensional PCA embedding gave a median per-state Spearman of 0.165 (range −0.37 to 0.64). · stated by the authors
  • Concordance with CellRank shows where the workflows differ, not which is biologically right; independent lineage or perturbational evidence would be needed. The step12 baseline also differs in environment, gene representation and kernel. · stated by the authors
  • Results depend on the choice of absorbing representatives. At the default r = 30, median Spearman against r = 200 was 0.60, and random 30-cell selections gave a median of 0.450 against the centroid-nearest choice. · noted in this summary
  • The float64 and CellRank agreement checks (Layers A/B), the kernel × terminal-set ablation and the threshold sweep all use one 5k fixture; only the strict backward-error test used a separate 1,600-cell synthetic chain. The 75k CellRank comparator is a single archived run whose Schur path is inferred from provenance. · noted in this summary

Who should read:Read this if you compute fate or absorption probabilities on large single-cell atlases without PETSc/SLEPc or much RAM, or want evidence on how terminal-state choice drives cross-tool fate discrepancies.

Reproducibility ledger

Nobody has reported trying to reproduce this paper yet. Did you replicate an experiment or run the code? Your report saves the next lab a week.

Sign in to file a reproducibility report.

Related papers

Similarity Map
SelectedSame fieldCross-field
THISKriukov '26Xing '25Xu '26Faure '22Dhapola '22Subedi '24
52% semantic matchBioinformatics
Emil Kriukov, Ekaterina Ivleva, Petr Y. Baranov·bioRxiv·Jul 30, 2026