Fallback Indexing for Non-Redundant Pathway Summaries

When a gene expression experiment is analyzed with functional enrichment, meaning a test of which curated gene groups ("pathways") are over-represented among the changed genes, the output is often hundreds of significant pathways that describe the same few biological programs. Summarizing this list amounts to picking a small set of representative pathways that together account for the enriched signal. Most tools judge redundancy by how many genes two pathways share. That breaks down in a specific, measurable way: gtCLIP, which aligns gene-set encoders with text encoders to cluster enrichment results, reports that over 80% of functionally related pathway pairs share zero genes. Under exact gene overlap, these pairs look completely unrelated.

Chinese web search faced the same failure. Indexing by dictionary words is precise, but it misses any term that is not in the dictionary or is segmented differently. The fix was a hybrid index: use words where they match, and fall back to character n-grams (short overlapping character substrings) only when they do not. We propose to treat gene identifiers as words and their finer-grained units as characters. Those finer units are character n-grams of gene symbols (IL6/IL6R, SLC25A-family prefixes) and word n-grams of pathway names. With this index, choosing a summary becomes a two-objective covering problem, which we solve with Pareto-front local search rather than greedy selection. The optimization literature shows that single-objective covering heuristics get stuck in poor solutions, while tracking the trade-off between coverage and summary size lets the search escape them.

Core Claim

Our claim concerns the search landscape of pathway summarization. Under exact gene overlap, the landscape is fragmented. Gene-disjoint but related pathways never "see" each other, so there is no single-swap path by which a local search can merge them. A summary that keeps both looks locally optimal even when it is redundant. This mirrors the observation in Dynamic Representations and Escaping Local Optima, which shows that changing the encoding of a search problem (shifting Gray codes, $x' = x \oplus s$) can make isolated local optima adjacent so that a simple hill-climber passes through them. Here, the change of representation is the fallback index. It adds neighborhood connections exactly where exact overlap is empty, and leaves precise gene-level evidence untouched where it exists.

Concretely, let $L$ be the leading-edge genes of the significant pathways, meaning the genes that drive each pathway's enrichment score. A summary $S$ is a set of pathways. A gene $g \in L$ is covered with weight 1 if some pathway in $S$ contains $g$. If no pathway in $S$ contains $g$, it is covered with weight $\lambda < 1$ when some pathway in $S$ contains a gene that shares a fallback unit with $g$. A fallback unit is a symbol character n-gram or a pathway-name word n-gram, after frequent units are removed. The search then trades off two objectives:

$$\max_S \; C(S)=\sum_{g\in L} w_g\, c_S(g), \qquad \min_S \; |S|,$$

Here $w_g$ is the gene's absolute enrichment contribution and $c_S(g)\in\{0,\lambda,1\}$ is its coverage level. Every remaining significant pathway is then assigned to the summary member with which it has the highest hybrid similarity, so the output is both a short list of representatives and a clustering of the rest.

Relation to Prior Work

Three groups of work supply parts of this proposal, and none combines them.

The first group supplies the indexing idea. Fallback indexing, in which character bigrams are used only for out-of-vocabulary terms, is described by Kam-Fai Wong et al. and Yun Xiao et al.. They report that it keeps the recall of character indexing while cutting index size by nearly 40%. Jianfeng Gao et al. show that adding unigrams stops short keywords from being hidden inside long compound words. ICT-Crossn fuses word, unigram and bigram scores with linear weights tuned by grid search. We reuse the fallback rule rather than always-on fusion. Fallback has one weight, $\lambda$, instead of three, and it keeps gene-level precision wherever gene-level evidence exists. None of these papers indexes biological entities.

The second group supplies the search method. Friedrich et al. prove that single-objective randomized local search can be trapped with unbounded approximation ratio on Set Cover. In the same setting, a multi-objective search called SEMO, which keeps every non-dominated trade-off solution, reaches an $O(\log n)$ approximation in polynomial time. DCCA shows that forbidding moves whose local context has not changed stops cycling in SAT local search. We use it only as an optional anti-cycling rule for pathway swaps. Neither work touches biological covering.

The third group motivates the problem and supplies the strongest competitor. gtCLIP solves redundancy with dense contrastive embeddings and offline agglomerative clustering. GSPA widens gene sets using node2vec neighborhoods in a protein-interaction network. It also reports that such embeddings underperform in poorly annotated disease areas, which constrains our design: we want fallback units that do not depend on interaction-network density. DeepSyn builds functional summaries by depth-first search over a literature graph and has no mechanism for escaping local traps.

Our proposal differs from gtCLIP in three ways. The index is sparse and inspectable rather than dense. Summarization is an explicit optimization with a full size-versus-coverage curve rather than a single clustering cut. And no training is required.

Research Program

The first component is the hybrid index. We will build it over the 12,612 GO, KEGG, Reactome and WikiPathways gene sets used by gtCLIP. The primary units are gene IDs. The fallback units are gene-symbol character n-grams of length 3 to 5, with prefix anchoring, plus pathway-name word unigrams and bigrams. Units that occur in more than a set fraction of genes, such as generic stems, are pruned.

The second component is the search. We will implement SEMO and Global SEMO over the two objectives above. Mutation adds, removes or swaps pathways, and a configuration-checking rule forbids re-adding a pathway until one of its hybrid-index neighbors has changed state. The output is the full Pareto front, from which a user picks a summary size.

The analysis has three parts. First, we will measure landscape fragmentation directly, as the fraction of single-swap neighborhoods with zero objective change under exact-only versus hybrid coverage. Second, we will measure how often greedy search terminates at a solution that SEMO dominates. Third, we will check where the fallback fires. If it fires mainly through gene-family prefixes, then HGNC naming is doing the work. HGNC is itself curated knowledge, and the paper must report this honestly as a source of leakage when pathways are defined from gene families.

Baselines

The do-nothing reference is the standard practice of reporting the top-$k$ pathways ranked by adjusted p-value. It is evaluated at the same summary sizes that our Pareto front produces. Any method that does not beat it on held-out coherence is not worth using.

The classical baseline is gene-overlap clustering: Jaccard or Szymkiewicz–Simpson agglomeration, and GeneSetCluster 2.0, which gtCLIP compares against. It is the tool practitioners use today. It is run on identical significant-pathway lists with its default thresholds and a matched grid over cluster counts.

The strongest existing method is gtCLIP. On its hematological malignancy benchmark it reports 3.3-fold higher within-cluster gene overlap and 3.9-fold higher silhouette score than its strongest baseline, and 92.4% mean NES sign coherence (the fraction of pathways in a cluster whose enrichment scores point in the same direction). On zero-shot COVID-19 data it reports 1.35× the within-cluster overlap of GeneSetCluster 2.0. No absolute silhouette or overlap values are reported in the file, so we will rerun gtCLIP ourselves with its released settings on the same inputs. Beating it means matching its NES sign coherence of at least 92.4% while improving the held-out coherence metrics described below at equal summary size.

The search-side ablations hold the hybrid index fixed and swap the optimizer: greedy weighted set cover, and simulated annealing with random restarts, each given the same number of objective evaluations as SEMO. The index-side ablations hold SEMO fixed. They compare exact-only coverage, always-on n-gram fusion with grid-tuned weights (the ICT-Crossn style), a GSPA-style node2vec fallback in place of character n-grams, and fallback-only n-grams. The last is our proposal, and this comparison isolates the fallback ingredient. All tuning budgets, including $\lambda$ and the fusion weights, are limited to the same small grid on one development cohort.

Why not just…?

Why not just use gtCLIP embeddings and cluster? This is the main competitor, and it may win on raw cluster separation. Our bet rests on two observations. Dense text alignment reaches only 51.3% Recall@5 when retrieving pathway definitions in gtCLIP's own evaluation, which suggests the embedding is imperfect. And clustering gives one cut rather than a coverage guarantee. If gtCLIP matches us on held-out coherence and on target-pathway retention at every summary size, the honest conclusion is that the sparse index offers interpretability and zero training cost but no accuracy gain. We will report it that way.

Why not just run greedy set cover? Greedy set cover already achieves a logarithmic approximation, and SEMO's worst-case guarantee in Friedrich et al. is of the same order, so greedy is a real threat. Pareto search has two possible advantages. It returns the whole size-versus-coverage curve in one run, and the three-level coverage weights break the clean structure that greedy relies on. The matched-evaluation comparison settles the question. If greedy is never dominated, we drop SEMO and the contribution reduces to the index.

Why not just use protein-interaction embeddings as the fallback? The GSPA-style ablation tests this directly. The GSPA paper's own report of weakness in poorly annotated diseases predicts that character-level fallback should do relatively better on the neurodegeneration-related GEO2KEGG datasets. If it does not, the interaction network is the better fallback, and we will say so.

Proposed Experiments

The first set of experiments uses gtCLIP's pathway corpus and its five blood-cancer GSEA cohorts, plus the zero-shot COVID-19 set. We report gtCLIP's own metrics: within-cluster overlap, silhouette and NES sign coherence. Within-cluster gene overlap favors any method that uses gene overlap, including ours, so the primary endpoint is a held-out coherence measure computed from information no method sees. That measure is the fraction of within-cluster pairs whose closest common GO-DAG ancestor lies within a fixed depth. The DAG is excluded from every index.

The second experiment uses the 42 GEO2KEGG datasets from GSPA, each of which has a known target KEGG pathway. We ask whether the target pathway, or its cluster representative, survives into summaries of size 5, 10 and 20. This is a direct test of whether compression throws away the biology. No reported result was found on Lacuna for summary-level target retention on GEO2KEGG. GSPA reports only that it beats GSEA in AUPRC on 75.8% of datasets.

Three decisive checks follow. First, the hybrid index must reduce the measured fraction of flat single-swap neighborhoods relative to exact-only coverage. If it does not, the landscape story is wrong. Second, fallback-only must beat always-on fusion. If it does not, the word-character fallback principle does not transfer to genes. Third, removing the gene-symbol n-grams while keeping the pathway-name n-grams tells us whether the gain comes from HGNC family naming or from text, which bounds the leakage concern.