Many of the proteins that control a cell's behavior, such as signaling kinases and short-lived transcription factors, are nearly invisible in gene-expression data. Their messenger RNA is scarce, and their activity often shows up as chemical modification rather than as a change in abundance. Network biologists handle this by treating known protein–protein interactions as a graph. They mark the genes that did change as "prizes" and search for the cheapest subgraph that connects them. Proteins that were never measured but sit on these cheap connecting paths, called Steiner nodes, become candidate hidden regulators. The approach has found unmeasured drivers that were later confirmed experimentally. Almost all of these analyses, however, run on bulk tissue, where the signal is an average over millions of mixed cells. An effect confined to a rare subpopulation is diluted away, and opposing effects in two cell types cancel out.
Single-cell RNA sequencing, which measures transcripts in each cell separately, looks like the fix. The obvious move is to run the Steiner search once per cell type and delete any protein the cell type does not express. That move has a flaw. Single-cell data capture only a small fraction of each cell's transcripts. The low-abundance regulators the method exists to find are exactly the genes that appear as zeros. A hard "must be expressed" filter therefore removes the true hidden regulators first. We propose to solve cell-type-specific Steiner forests jointly across cell types. Each protein's admissibility in a cell type becomes a soft cost derived from the statistical evidence that its zeros are real, and that evidence depends on how many cells were observed. Related cell types share network structure, so rare populations can borrow statistical strength from their neighbors.
Core Claim
A zero count for a gene means very different things in a cell type with 5,000 cells and in one with 40 cells. A cell-type-specific latent-node method that ignores this will fail in one of two ways. Without an expression filter, it routes paths through proteins that are absent from that cell type. With a hard filter, it deletes real low-copy regulators. We claim that replacing the hard filter with a per-cell-type probability that a protein is present fixes both failures, and that coupling the forests along the cell-type hierarchy recovers regulators in rare populations that independent per-type solves miss. Both claims can be tested against ground truth, because one of the benchmarks pairs single-cell data with deep sorted-population bulk RNA sequencing of the same cell types.
Research Program
The method starts from the prize-collecting Steiner forest objective used by Omics Integrator and the PCSF R-package. Those tools find a forest that trades uncollected prizes against edge costs, and they already penalize high-degree hub proteins. We reuse them as the solver and their hub penalties as a fixed ingredient.
Two things change. The first is the node-presence term. For cell type $k$ with $n_k$ cells, we estimate $\pi_k(v)$, the posterior probability that gene $v$ is truly expressed in type $k$. We use a Poisson–Gamma model of pooled counts with a per-cell capture efficiency $q$ and a gene-level prior on mean expression $\mu_v$ fitted across the atlas. Under this model, the chance of seeing only zeros in a type where the gene is present at mean $\mu$ is roughly $\exp(-n_k q \mu)$. As a result, zeros are strong evidence of absence only when $n_k q \mu$ is large, which is the formal version of "rare cell types and scarce transcripts deserve the benefit of the doubt."
The second change is that the $K$ forests are solved together, so they tend to share edges between related cell types. Writing $F_k$ for the forest in type $k$ with edge set $E_k$, the joint problem is
$$\min_{F_1,\dots,F_K} \sum_{k}\Big[\sum_{v\notin F_k}\beta\, p_k(v) + \sum_{(u,v)\in E_k}\big(c(u,v) - \lambda\log\pi_k(u)\pi_k(v)\big)\Big] + \gamma\sum_{k<k'} w_{kk'}\,|E_k \,\triangle\, E_{k'}|.$$
Here $p_k(v)$ is the prize from within-type differential expression. $c(u,v)$ is the hub-penalized interaction cost. $\lambda$ sets how strongly presence evidence counts. The symbol $\triangle$ denotes the set of edges used by one forest but not the other. The weight $w_{kk'}$ is a similarity between cell types taken from the Cell Ontology hierarchy, the same hierarchy POPPY uses for contrastive alignment.
The coupling term is motivated by Multi-Level Steiner Trees, which shares network infrastructure across nested terminal tiers but has only ever been tested on synthetic random graphs. Our coupling is softer: it penalizes disagreement between forests rather than requiring the terminal sets to be nested. It fits sibling cell types that are not subsets of one another.
We will solve the joint problem by alternating reweighting. Each forest is re-solved with the fast PCSF heuristic, and edges used by ontologically close forests get a discount. The PCSF package reports 101 seconds per breast-cancer instance, compared with 1920 seconds for message passing (PCSF). At that speed, roughly 30 cell types over ten rounds plus randomized robustness runs fits comfortably on a small cluster. For bulk-only studies, the same machinery accepts deconvolved cell-type prizes as input. In that mode the per-type prizes come from cell-weighted fold-changes as in scMappR, rather than from within-type single-cell differential expression.
Baselines
The naive reference point is bulk or pseudobulk Steiner forest analysis with Omics Integrator's hub penalty and its bulk-derived negative prizes for unexpressed genes (Omics Integrator). This is the standard practice in the glioblastoma studies (Köhler-style interactome–epigenome map, patient-specific glioblastoma pathways). It runs on the same pseudobulk profiles with the same interactome. The outcome this baseline should show is that it misses rare-type and cancelling signals.
The strongest existing method that assigns cell-type specificity to expression changes is scMappR. It reweights bulk fold-changes by deconvolved cell proportions and passes the resulting gene lists to enrichment analysis. The only figure the file reports for it is an average correlation (rho) increase of 0.0471 in cell-type specificity over bulk differentially expressed genes on the Monaco PBMC benchmark. No reported result was found on Lacuna for any latent-node method recovering held-out or unmeasured regulators on these benchmarks. This means we must construct that evaluation ourselves, and a positive result there cannot be read as beating a published number. To compare on scMappR's own terms, we will check whether the genes in our forests, including Steiner nodes, correlate with sorted-population fold-changes at least as well as scMappR's re-ranked lists. That is the only metric on which a published number exists.
The most dangerous baseline is independent per-cell-type PCSF, run in two versions: with no expression filter and with a hard detection filter (at least one count across the type's cells). It uses identical prizes, interactome, hub penalty, and the same total solver budget. For fairness, $\beta$, $\lambda$, and the hub penalty for every method are tuned by the same grid search on a held-out cell-type split. The ablations are the soft presence term alone with $\gamma=0$, and coupling alone with a hard filter. Together they separate what the presence model contributes from what the coupling contributes. Beating these baselines means higher held-out-regulator recall at matched forest size, and higher precision of Steiner nodes against sorted bulk expression, with the gain concentrated in cell types with few cells.
Why not just…?
Why not just run PCSF separately on each cluster and drop unexpressed genes? This is the obvious version. We expect it to fail precisely on the target nodes, because transcription-factor and kinase transcripts are among the most dropout-prone. That is a prediction, not an established result. The hard-filter baseline and the in-silico dropout experiment below test it directly. If hard filtering performs as well as the soft term in the cell types that matter, the presence model is unnecessary and we will say so.
Why not deconvolve, then run GSEA or GO enrichment per cell type? Enrichment scores genes against predefined categories and cannot name a specific unmeasured protein that connects the measured hits. Unmeasured connectors are the objects that were validated in the glioblastoma work: CREBBP, β-catenin, and p300 in the interactome–epigenome map, and MEK1, confirmed active in 7 of 8 xenografts, in the patient-specific study. Enrichment can still be a strong rival on the scMappR-style correlation metric, and we report it there.
Why not use network propagation such as PageRank or random walk with restart? Propagation spreads weight over the whole graph and concentrates it on hubs. SubNetDL had to prune to 253 known cancer drivers to make propagated scores usable, which rules out discovering new connectors. We include per-type random walk with restart, thresholded to the same node count as our forests, as a baseline. If it matches us on held-out recall, the combinatorial machinery is not earning its cost.
Why not simply rely on the coupling and skip the probabilistic mask, or the reverse? The two ablations answer this. The coupling should matter little for abundant cell types and substantially for rare ones. If the gain does not grow as cell counts shrink, we drop the coupling term.
Proposed Experiments
The primary test uses the Monaco PBMC resource, accessed through scMappR: 29 sorted immune populations with deep bulk RNA sequencing alongside single-cell profiles. We run every method on the single-cell data only. For each Steiner node assigned to a cell type, we check expression in that population's sorted bulk profile, which suffers far less dropout. Steiner-node precision is the fraction of assigned nodes that are expressed there. We then subsample cells per type (for example 2,000, 500, 100, and 30) to trace precision and recall as a function of $n_k$. This is where the method should separate from the baselines.
The second test is in-silico dropout. We take regulators that are clearly expressed in a cell type, remove their prizes, and thin their counts binomially down to realistic capture rates. We then ask whether each method recovers them as Steiner nodes in the correct cell type. This directly measures what hard filtering destroys.
The third test is cancellation and dilution. We build pseudobulk mixtures from Onek1k-scale PBMC data and Kassandra-style simulated profiles (POPPY). Into these we plant opposing changes across two cell types, and changes restricted to a 2–5% population. We score bulk PCSF, scMappR-fed PCSF, and our method on recovering the planted modules.
The last test is biological. On the Valle Duraes kidney regeneration data, where scMappR detected roles for cell types making up under 5% of the tissue, we ask whether the forests for rare types name upstream regulators absent from both bulk forests and enrichment output. We report these only as hypotheses for perturbation follow-up, not as validated findings.
The decisive outcome is the Monaco subsampling curve. If soft presence plus coupling beats independent hard-filtered PCSF on sorted-bulk precision and held-out recall, with a margin that grows as $n_k$ shrinks, the proposal holds. If the curves overlap, the simple per-cluster pipeline is sufficient.
References
- Network-Based Interpretation of Diverse High-Throughput Datasets through the Omics Integrator Software Package
- PCSF: An R-package for network-based interpretation of high-throughput data
- Cross-modal transfer learning for mapping bulk transcriptomes at cellular level
- Multi-level Steiner Trees
- Single-cell mapper (scMappR): using scRNA-seq to infer cell-type specificities of differentially expressed genes
- Linking Proteomic and Transcriptional Data through the Interactome and Epigenome Reveals a Map of Oncogene-induced Signaling
- Network Modeling Identifies Patient-specific Pathways in Glioblastoma
- A network-based deep learning model integrating subclonal architecture for therapy response prediction in cancer
- Count Bridges enable Modeling and Deconvolving Transcriptomic Data