Escaping Pathway Traps in Genetic Screen Design

Biologists running genome-wide CRISPR screens, in which genes are knocked out and the effect on a cell phenotype is measured, increasingly let a machine-learning model choose which genes to test next. The best current method, BioBO, runs functional enrichment analysis after each round. Enrichment analysis is a statistical test that asks whether the hits so far concentrate in a known biological pathway. BioBO then steers the next batch toward untested genes in the pathways that test flagged. This works well, but it has an obvious risk: the search can lock onto the first pathway that lights up and never find a stronger one elsewhere. We argue that this trap follows from the shape of the discovery objective, and that fixing the objective works better than adding noise. A pathway only becomes detectable once several of its genes have been tested and found to be hits. The value of probing a new pathway is therefore near zero for the first gene and jumps once a threshold is crossed. The objective lacks diminishing returns, so any method that adds genes one at a time will keep choosing the familiar pathway.

The proposal is to plan batches over pathway probes, meaning committed bundles of genes large enough to make an unexplored pathway testable. Recast this way, batch selection becomes a coverage-style problem that a greedy algorithm handles well, and each round comes with an error bound that can be computed from the data. We will test on the GeneDisco screens whether this finds more distinct true pathways, and finds them sooner, than BioBO, without giving up raw hit yield.

Core Claim

Two properties matter here. A set function has diminishing returns (it is "submodular") if adding an element to a small set helps at least as much as adding it to a larger one. When that holds, the greedy algorithm that repeatedly adds the best next element is guaranteed to reach a constant fraction of the optimum. Premature convergence is the failure mode in which a search collapses onto an early, suboptimal region. Our claim is that in enrichment-guided screen design these are the same phenomenon.

Write $q_g$ for the surrogate model's posterior probability that gene $g$ is a hit. Write $h_p$ for the hits already observed in pathway $p$. Write $t_p$ for the number of hits needed for the enrichment test (a hypergeometric test) on $p$ to pass at level $\alpha$ given its size. The value of a batch $B$ for discovering new pathways is then

$$F(B) = \sum_{p \notin \mathcal{E}} w_p \Pr\Big[h_p + \sum_{g \in B \cap p} y_g \ge t_p\Big] + \lambda \sum_{g \in B} q_g ,$$

where $y_g \sim \text{Bernoulli}(q_g)$, $\mathcal{E}$ is the set of pathways already enriched, $w_p$ weights pathways (uniform by default), and $\lambda$ trades pathway discovery against raw hit count. Each pathway term is the upper tail of a sum of Bernoullis. Below the threshold, that tail grows convexly in the number of genes added, which is exactly where diminishing returns fail.

A single gene in an unexplored pathway gets almost no credit, while one more gene in a nearly enriched pathway gets a lot. BioBO's prior and every one-gene-at-a-time rule inherit this bias. This is the same all-or-nothing structure that defeats greedy selection in conservation corridor design, as documented in Fast Combinatorial Algorithm for Optimizing the Spread of Cascades.

The fix is to change the elements being chosen. A probe $(p, m)$ is the $m$ untested genes of $p$ with the highest $q_g$, where $m$ is the smallest number that brings the expected hit count up to the threshold. Over probes, each pathway term sits near or past its inflection point and behaves approximately concavely. The batch-size constraint becomes a constraint on the number of distinct genes across the chosen probes. Because pathways share genes, that count is a coverage function and so has diminishing returns.

The problem is therefore to maximize an approximately submodular benefit under a submodular budget. This is the problem class for which Maximizing submodular functions under submodular constraints gives a greedy algorithm with a guarantee of the form $F(X) \ge (1-1/e)F(\text{OPT}) - A$. The additive error $A$ can be computed for each instance. The new contribution is three things together: the diagnosis that enrichment-driven entrapment comes from a threshold-shaped objective, the reformulation over probes, and the per-round bound.

Research Program

We will build the method on top of BioBO's own surrogate, a Bayesian neural network fed Achilles dependency scores, Gene2Vec, and GenePT embeddings. This keeps any gain attributable to batch construction rather than to a better model. The steps are as follows.

First, estimate $q_g$ from the posterior at each round. Second, compute $t_p$ from the hypergeometric test given the current set of tested genes. Third, build a probe for each pathway not yet enriched. Fourth, run the greedy algorithm under a submodular constraint (SCSK-C) and fill any leftover batch slots with top-$q_g$ genes, which covers the $\lambda$ term.

Two design choices come from prior work. The first concerns the candidate pathway collection. Consolidated databases contain many near-duplicate pathways, and Using set theory to reduce redundancy in pathway sets shows that greedy set cover over ConsensusPathDB removes 74% of redundancy while still covering every gene. We use its reduced collection so that probes do not waste budget rediscovering one pathway under several names. That same paper also constrains our design: plain greedy covering favors giant KEGG terms. Because $t_p$ grows with pathway size, our objective should naturally discount large pathways, and we will check that it does.

The second choice concerns the algorithmic guarantee. Padmanabhan et al. report that their additive error falls to zero on sparse networks but reaches 43% of the objective on the dense Facebook graph. Pathway gene overlap may well sit in that dense regime. We will therefore report $A$ and an empirical estimate of the submodularity ratio $\gamma$, following the approach of Greedy Sampling of Graph Signals, at every round. If $A$ turns out to be large, that is an honest finding about where guarantees for this problem break. As an alternative solver we will use UP from Regularized Unconstrained Weakly Submodular Maximization, with the budget replaced by a per-gene cost. UP is deterministic and nearly linear in time, but it only handles costs that add up gene by gene, so comparing the two solvers shows what the submodular budget contributes.

A known tension shapes the evaluation. Divergence-Guided Particle Swarm Optimization found that forced exploration hurts on landscapes with a single peak. By analogy, if a screen's hits really do sit in one pathway, probes spent elsewhere are wasted. Our objective has a built-in safeguard: if no unexplored pathway has a meaningful chance of reaching its threshold, $F$ reduces to the hit-yield term. We will measure whether that safeguard is enough.

Baselines

The naive reference points are random acquisition and plain uncertainty-driven acquisition. For the latter we use BALD and BADGE, as benchmarked in GeneDisco, which found that these methods dig into clusters of hits. We also include K-Means/Coreset geometric diversity, which GeneDisco found poor at finding hits. We include it to confirm that diversity in the embedding space is the wrong kind of diversity.

The strongest competitor is BioBO, because it already uses enrichment inside the acquisition loop and is exactly the method whose trapping we claim to fix. For BioBO, no reported absolute hit-discovery numbers were found on Lacuna. The reported figures are 25–40% better labeling efficiency than standard methods and the best result in 23 of 24 experimental settings. We will rerun BioBO with its published surrogate and prior-decay schedule on identical data splits, batch sizes, round counts, and seeds. Its hyperparameters get the same tuning budget as our $\lambda$ and $m$.

We also adapt the strategy-space batch method of Exploiting Strategy-Space Diversity for Batch Bayesian Optimization to the discrete setting. That method builds batches from the Pareto front of posterior mean against posterior uncertainty, and it is the strongest general remedy for premature convergence in the file. In our adaptation, the front is computed exactly over the untested genes.

Beating the baselines means two things. The first is statistically higher recall of ground-truth pathways at a matched budget. The second is hit yield within 5% of BioBO's, with no loss beyond that margin.

Three ablations isolate the key ingredient. The first runs greedy on $F$ with single genes as elements and no probes, which tests whether the reformulation, rather than the objective alone, is what matters. The second commits random probes: it picks an unexplored pathway uniformly at random and spends $m$ genes on it. The third keeps probes but replaces the coverage budget with a gene-by-gene cost solved by UP.

Why not just…?

Why not just decay BioBO's prior faster, or add ε-random exploration? Spreading random genes across the genome places about one gene in each pathway. Under the threshold objective above, that almost never makes a new pathway testable, so our analysis predicts this alternative fails for the same reason BioBO stalls. The results of Multiple-Frequencies Population-Based Training point the same way in a different setting: at 1 billion steps in the Humanoid task, random search reached an IQM reward of 17,713 against 23,793 for structured diversity preservation. We run faster-decay and ε-random variants of BioBO directly, so this is settled empirically.

Why not just commit random pathway probes? This is the real threat, and the reason we run it as an ablation. If probes into randomly chosen pathways match our method, then the whole contribution is "commit enough genes to cross the threshold," and the optimization machinery is unnecessary. We expect the optimized version to win because it chooses pathways where the posterior makes crossing the threshold likely and it shares genes across overlapping probes. The planted-trap experiment below is designed to show whether that expectation holds.

Why not just use Pareto batches of posterior mean and uncertainty? That method diversifies over trade-offs between exploiting and exploring, but it has no notion of pathways. It can therefore still scatter its uncertain picks across pathways, one gene each. It is a strong generic baseline, and if it recovers pathways as well as our method, our claim that the objective's structure matters is weakened.

Proposed Experiments

We will use the GeneDisco assays for IL-2, IFN-γ, T-cell proliferation, and leukemia vulnerability to natural killer cells, plus the Tau and SARS-CoV-2 assays used by BioBO. Runs use batch sizes of 32 and 128 over a fixed number of rounds, with 10 seeds each.

For each assay, ground-truth pathways are those that pass enrichment analysis on the top 1% of the full screen, computed over the reduced ConsensusPathDB collection. The main metrics are cumulative hit recall and the fraction of ground-truth pathways that become enriched among the acquired hits. Two diagnostics measure entrapment directly: the round at which each true pathway is first discovered, and the share of each batch spent in pathways that are already enriched.

The decisive check is a semi-synthetic planted trap. We relabel a real screen so that one pathway produces moderate early hits while a second, stronger pathway gives no signal in the initial random batch. We then measure how many rounds each method takes to find the second pathway.

As a control in the other direction, we run assays whose hits concentrate in a single pathway. Our method should match BioBO there, which is the single-peak case that hurt the swarm repulsion method.

Throughout all runs we log the additive error $A$ and the empirical submodularity ratio $\gamma$. This tells us whether the per-round guarantee means anything on biological pathway overlap, or whether pathway overlap is dense enough that the guarantee becomes loose, as it did on the Facebook graph.