Gene-Set Permutations and Their Limitations

What a Gene-Set Permutation Holds Fixed

A ranked enrichment analysis asks whether the members of a specified gene set occur unusually near one end of an ordered gene list. One way to assess that pattern is to hold the observed ranking fixed and compare the set’s enrichment score with scores from randomly selected gene sets of the same size. This is called a gene-set permutation or gene-set randomization.

The procedure addresses a particular reference question: if a set of this size were placed uniformly among the genes in the tested universe, how often would it receive a score at least as extreme as the observed score? It does not reshuffle samples or recompute the gene-level statistics. Consequently, it can be used when sample labels cannot be permuted, but it does not reproduce the dependence among gene-level statistics that may result from correlated expression.

The tested universe matters: it consists of genes eligible to appear in the ranking, not every gene known in biology. The set should be intersected with that universe before its size is determined. Let \(m\) denote the number of distinct set genes remaining in the universe. A valid size-matched draw must contain exactly \(m\) distinct genes, sampled without replacement.

The ranking and the score definition must be fixed before interpreting this reference distribution. In a weighted GSEA score, the hit increment depends on the absolute gene-level statistic raised to a specified power; in an unweighted score, all hits receive equal increments. Whichever score was used for the observed set must also be used for every sampled set. The running-sum score and its direction are described here explicitly so the calculation is self-contained.

Running-Sum Score and the Random-Placement Reference

For an unweighted score, walk down the ranking. When gene \(r_i\) belongs to the set, increase the running sum by \(1/m\). When it does not, decrease it by \(1/(N-m)\). The enrichment score (ES) is the largest absolute departure of the running sum from zero, given the sign of the departure where that maximum occurs. Thus, a positive ES indicates concentration near the top of the ranking; a negative ES indicates concentration near the bottom. Weighted scores change the hit increments but retain the same principle of comparing a set’s placement with the ranking.

Here \(X_k\) is the number of set members among the first \(k\) ranked genes, and \(R_k\) is the running sum after position \(k\). Under uniform random placement, each gene has probability \(m/N\) of being selected, so the expected number of hits in the first \(k\) positions is \(E(X_k)=km/N\). Substitution shows that the expected running sum at each fixed position is zero:

This argument explains why random sets provide a centered reference for the running sum at any one position. It does not give the distribution of the maximum absolute departure: positions along a walk are dependent, and the maximum is a nonlinear summary. The ES reference distribution is therefore obtained by calculating the full score for each sampled set, rather than by treating the \(R_k\) values as independent.

Estimating a Tail Probability by Sampling

In practice, the number of possible size-\(m\) sets, \(\binom{N}{m}\), is often too large to enumerate. Instead, draw \(B\) random sets and calculate their scores. For a pre-specified positive-tail question, count the sampled scores that are at least as large as the observed positive ES. Using “at least as large” includes ties, which makes the tail definition explicit.

For a negative observed ES, the analogous directional calculation counts sampled scores that are less than or equal to the observed score. If the scientific question is explicitly two-sided, the tail rule must be specified in advance and applied consistently—for example, by comparing absolute scores. A positive-tail count should not be relabelled as a two-sided probability after inspecting the result.

Worked Reference Distribution and a Sampling Check

The permutation procedure is straightforward, but its interpretation depends on what is randomized. The following example traces a small calculation and shows why the ranking remains unchanged throughout.

A practical workflow is to define the eligible universe and observed set first, then calculate the observed score, sample size-matched sets, and apply the identical scoring rule to each draw. If the rank statistic or set membership changes during the sampling loop, the resulting distribution no longer represents the stated fixed-ranking reference.

What the Reference Distribution Assumes—and What It Misses

Uniform size-matched sampling assumes that, under the reference being used, every size-\(m\) subset of the tested universe is an equally appropriate placement of a set on the fixed ranking. It also assumes that the universe is correctly specified and that the observed and sampled scores are calculated comparably. This random-placement assumption can be useful as a descriptive benchmark, but it can be implausible when genes differ systematically in how likely they are to appear near the top or bottom of the ranking.

The key limitation is that randomizing set membership does not preserve the correlation structure among genes. Expression measurements for genes in a biological pathway can move together, and their gene-level statistics can consequently be correlated. A uniformly sampled set may combine genes that are unrelated in expression, while the observed set may contain a block of strongly correlated genes. The sampled scores then do not fully represent the behavior expected from a set with the observed dependence structure. Depending on the pattern of correlation and the score, the resulting tail assessment can be too liberal or too conservative; the direction is not guaranteed.

Phenotype permutations provide a useful contrast. They shuffle sample labels when the study design permits valid label exchangeability, then recalculate gene-level statistics and the ranking. Because the sample data are retained jointly, correlations among genes are generally carried through to the permuted statistics. This approach has its own conditions: the phenotype labels must be exchangeable under the null, and paired, blocked, or otherwise structured designs require permutations that respect that structure. Gene-set permutations avoid the need to permute labels, but trade that advantage for a reference based on random gene placement.

Neither procedure is automatically valid simply because it produces many permutations. The earlier material on phenotype permutations for GSEA significance concerns the sample-label route; the choice here depends on whether its design assumptions are defensible and whether a fixed-ranking random-placement question is appropriate.

Diagnostics, Alternatives, and Common Pitfalls

• Check universe and identifiers. Confirm that set genes are matched to the same tested universe used for the ranking. An incorrect universe or duplicated identifiers changes \(N\), \(m\), and the sampled reference.
• Check the sampling mechanism. Verify that every draw has exactly \(m\) distinct genes. Sampling with replacement, or accidentally varying set size, does not implement the stated randomization.
• Check score consistency. Use the same ranking, weighting exponent, tie handling, and ES convention for the observed set and all sampled sets.
• Check Monte Carlo stability. Report \(B\) and \(b\). A small number of draws gives coarse tail resolution; repeat with more draws when feasible, particularly for small estimated tail probabilities.
• Check exchangeability plausibility. Consider whether genes have differing rank propensities or whether the set is unusually correlated. If uniform placement is a poor reference, the resulting tail probability may not answer the intended question.

A common mistake is to say, “The gene-set permutation preserves gene-gene correlation because the observed ranking came from correlated expression.” The correction is that the ranking is indeed held fixed, but the sampled sets change which genes are grouped together. The observed ranking may reflect correlation, while the random-set reference does not preserve the observed set’s correlation structure. Keeping the list fixed is not the same as preserving dependence within every randomized set.

Another mistake is to describe \(b/B\) as the plus-one estimate, or to report \((b+1)/(B+1)\) as the literal fraction of sampled sets that exceeded the observed score. These are distinct calculations and should be labelled separately. Likewise, a small reference tail probability means the observed score is unusual under the specified random-placement reference; it is not the probability that the pathway is null, nor a direct measure of causal or biological importance.

Gene-set permutations are most useful when the fixed-ranking random-placement comparison is scientifically meaningful, sample-label permutations are unavailable or inappropriate, and the limitations of the reference are acknowledged. They are not a universal replacement for phenotype permutations or for methods designed to account for dependence. The appropriate interpretation is conditional on the ranking, universe, score, and randomization scheme used.