Deriving Over-Representation From the Hypergeometric Distribution

Why Pathway Over-Representation Has a Sampling Model

Suppose a differential-expression analysis produces a set of selected genes, and a pathway is a fixed set of genes of interest. Over-representation asks whether the selected set contains an unusually large number of members of that pathway. The key probability calculation is not based on drawing genes independently: the selected set has a fixed size and is drawn from a finite tested-gene universe. That makes the overlap count hypergeometric.

The tested-gene universe is the set of genes eligible to be selected by the analysis. The pathway size used here is not necessarily the number of genes annotated to the pathway in a database; it is the number of pathway genes that are also in the tested-gene universe. Both quantities must refer to the same universe.

Definition: Let $N$ be the number of genes in the tested-gene universe, $K$ the number of those genes in a specified pathway, and $n$ the number selected. Under the null model, the selected set is a uniformly random subset of size $n$ from the $N$ genes. Let $X$ be the number of selected genes in the pathway. Then $X$ has a hypergeometric distribution with parameters $N$, $K$, and $n$.

This model makes a precise conditional statement: given the universe, pathway membership, and selection count, every subset of $n$ genes is equally likely under the null. It does not say that the original expression measurements are random draws from a gene population, or that each gene is independently selected. The selection rule and analysis that produced the selected set are held fixed; the null randomizes which $n$ eligible genes would be selected.

Deriving the Hypergeometric Probability

There are $\binom{N}{n}$ possible subsets of size $n$ from the universe. To obtain exactly $k$ pathway genes, choose $k$ of the $K$ pathway genes and $n-k$ of the $N-K$ genes outside the pathway. Each such pair of choices gives one selected set, and every selected set with overlap $k$ is counted exactly once. Dividing the number of qualifying sets by the number of all possible sets gives the probability.

P(X=k)=\frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}

The feasible overlap values are integers from $\max(0,n-(N-K))$ to $\min(K,n)$. Values outside this range have probability zero: for example, the overlap cannot exceed the pathway size or the total number selected, and selection cannot require more non-pathway genes than exist. The binomial coefficient $\binom{a}{b}$ counts the ways to choose $b$ objects from $a$, with value zero if $b<0$ or $b>a$.

Over-representation p-value: If $x$ pathway genes are observed among the $n$ selected genes, the upper-tail p-value is the null probability of observing an overlap at least this large: $$ P(X\ge x)=\sum_{k=x}^{\min(K,n)} \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}} $$ If $x$ exceeds the feasible maximum, the observed data and stated counts are inconsistent. If $x$ is at or below the feasible minimum, the upper-tail probability is 1.

The upper tail is used because the question is whether the pathway has more selected genes than expected under the null. The p-value is computed from the entire null distribution, including the probability of the observed overlap and all larger feasible overlaps. It is not the probability that the null model is true, nor does it measure the size of a biological effect.

Worked Example: A Small Universe and an Exact Tail Probability

Consider a hypothetical tested-gene universe of $N=20$ genes. A pathway contains $K=5$ of them, and $n=4$ genes were selected. Suppose $x=2$ selected genes belong to the pathway. Assume the pathway and selected set are both restricted to this same universe, the selected genes are distinct, and the null treats every four-gene subset as equally likely.

The possible overlaps are 0, 1, 2, 3, and 4. For the upper tail, calculate the probabilities for $k=2,3,4$. There are $\binom{20}{4}=4{,}845$ possible selected sets in total.

P(X\ge 2) =\frac{\binom{5}{2}\binom{15}{2} +\binom{5}{3}\binom{15}{1} +\binom{5}{4}\binom{15}{0}}{\binom{20}{4}}

Substituting the combinations gives $\binom{5}{2}\binom{15}{2}=10(105)=1{,}050$, $\binom{5}{3}\binom{15}{1}=10(15)=150$, and $\binom{5}{4}\binom{15}{0}=5(1)=5$. Therefore, $P(X\ge2)=(1{,}050+150+5)/4{,}845=1{,}205/4{,}845\approx0.2487$.

Under this model, about 24.9% of random four-gene subsets would contain at least two of the five pathway genes. This overlap is not especially unusual by the upper-tail calculation alone; the p-value is not evidence that the pathway is enriched just because the observed overlap is greater than zero.

Expected Overlap and What the Tail Measures

The expected overlap is $E(X)=nK/N$. One way to see this is to write $X$ as the sum of $K$ indicator variables, one for each pathway gene, where an indicator is 1 if that gene is selected and 0 otherwise. Each pathway gene has probability $n/N$ of being included in a uniformly chosen subset of size $n$. By linearity of expectation, the expected sum is $K(n/N)$.

This expectation gives a useful reference point, but it is not itself a p-value. The upper-tail calculation also accounts for the spread and discreteness of the overlap distribution. For instance, an observed count slightly above expectation may still be common, while a more extreme count may lie in a small-probability tail.

Worked Example: A Small Upper-Tail Probability

In a hypothetical universe of $N=30$ tested genes, a pathway contains $K=6$ genes. Five genes are selected, and three are in the pathway, so $n=5$ and $x=3$. Assume all five are distinct members of the universe and that the fixed-size uniform-selection null is appropriate.

The expected overlap is $nK/N=5(6)/30=1$ gene. The observed overlap is 3. The possible overlaps at least as large as 3 are 3, 4, and 5, and the total number of five-gene subsets is $\binom{30}{5}=142{,}506$.

P(X\ge3) =\frac{\binom{6}{3}\binom{24}{2} +\binom{6}{4}\binom{24}{1} +\binom{6}{5}\binom{24}{0}}{\binom{30}{5}}

The numerator terms are $20(276)=5{,}520$, $15(24)=360$, and $6(1)=6$. Thus, $P(X\ge3)=5{,}886/142{,}506\approx0.04130$. Under the stated null, about 4.13% of random five-gene subsets would have at least three pathway genes. This is a relatively small upper-tail probability, but it does not establish a causal role for the pathway or describe the size of a biological effect.

Assumptions, Diagnostics, and Alternatives

The calculation is exact for its stated random-subset model. Before interpreting it, check that the inputs describe the same analysis universe and that the observed overlap is counted correctly. In particular, identifiers should be mapped consistently, duplicate gene identifiers removed according to the analysis definition, and pathway members outside the tested universe excluded from $K$. The selected count $n$ must count distinct eligible genes, and $x$ must count the intersection of the selected set and the pathway.

The central modeling assumption is uniformity: under the null, every eligible gene has the same chance of appearing in a selected subset, conditional on exactly $n$ selections. This can be implausible if genes differ systematically in their probability of being detected or selected, for example because of expression level, gene length, or other features of the selection procedure. Correlated gene-level evidence can also make the actual selection process depart from uniform random selection. The hypergeometric formula still computes the probability under its defined null; a small p-value does not repair a poorly matched null model.

A binomial model with $n$ independent draws and pathway probability $K/N$ is a possible approximation in some settings, but it treats draws as independent and does not enforce the finite-population constraint. The hypergeometric model is the natural exact choice when exactly $n$ distinct genes are selected from $N$ without replacement. Simulation can approximate the same null by repeatedly sampling subsets of size $n$, but it introduces Monte Carlo error; the exact sum is preferable when it is computationally practical.

Common warning signs include a reported pathway size larger than the universe, an observed overlap larger than $\min(K,n)$, or an unexpectedly different result after correcting gene mapping or duplicates. Such problems usually indicate inconsistent inputs rather than an unusual statistical result. Also, many pathway p-values are often examined in a single analysis. The single-pathway hypergeometric p-value describes one test under its null; it does not by itself account for the number of pathways examined.

Worked Example: Checking the Inputs Before Calculating

Suppose a hypothetical analysis has $N=12$ tested genes, of which $K=4$ are in a pathway. Three genes are selected, and two selected genes are pathway members. Assume all counts refer to the same universe and the selections are distinct. First check feasibility: $0\le2\le\min(4,3)=3$, so the overlap is possible. The possible upper-tail values are 2 and 3.

P(X\ge2) =\frac{\binom{4}{2}\binom{8}{1} +\binom{4}{3}\binom{8}{0}}{\binom{12}{3}} =\frac{6(8)+4(1)}{220} =\frac{52}{220} \approx0.2364

The expected overlap is $nK/N=3(4)/12=1$, while two were observed. The upper-tail probability is approximately 0.2364. If instead someone reported an overlap of 4 with only 3 selected genes, the calculation should stop: $x=4$ violates the maximum possible overlap, so at least one input or count is wrong.

Common Mistakes and Interpretation

Using the wrong pathway size. Counting all annotated pathway genes, including genes outside the tested universe, makes $K$ incompatible with $N$. Use the pathway-universe intersection.
Using the probability of exactly the observed count. Over-representation asks for at least the observed overlap, so sum the probabilities for $x,x+1,\ldots$, not just $P(X=x)$.
Assuming independent gene selections. The fixed-size selection model is without replacement. The hypergeometric distribution accounts for the resulting dependence among inclusion indicators.
Calling a p-value the probability that a pathway is enriched. It is a probability of outcomes at least as extreme under the specified null model, not a posterior probability about the pathway.

Key takeaway: For a fixed-size selected set, compare the observed pathway overlap with the hypergeometric upper tail. The calculation is exact under uniform selection of $n$ distinct genes from a shared universe of $N$, with pathway size $K$.

Check Your Understanding

For each question, identify the relevant counts and use the fixed-size uniform-selection model. Solutions are included below.

A universe has $N=10$ genes, a pathway has $K=3$, and $n=2$ genes are selected. What is the expected overlap?
For $N=10$, $K=3$, and $n=2$, calculate the upper-tail probability for an observed overlap of $x=2$.
A pathway contains 18 annotated genes, but only 12 are in the tested universe. Which pathway size belongs in the hypergeometric calculation?
Why is an observed overlap $x=4$ impossible when $n=3$, regardless of the values of $N$ and $K$?

Solutions. (1) $E(X)=nK/N=2(3)/10=0.6$ gene. (2) The only tail value is $k=2$, so $P(X\ge2)=\binom{3}{2}\binom{7}{0}/\binom{10}{2}=3/45\approx0.06667$. (3) Use $K=12$, the number of pathway genes in the tested universe; the other six genes are not eligible for selection. (4) The overlap cannot exceed the total number selected, so $x\le n=3$; an input reporting four selected pathway genes is inconsistent.