Why Permutations Need Calibration
A spatial statistic can be calculated for a gene and compared with a reference distribution to assess whether its observed pattern is unusual. A permutation test builds that reference distribution by rearranging data in ways allowed under a specified null hypothesis. The central issue is not whether the rearrangements are numerous or easy to generate. It is whether the rearrangements are justified by the null.
For example, randomly shuffling expression values among every spot treats the spots as interchangeable under the null. That can be reasonable when their expression values have the same distribution under the null. It is not reasonable merely because the spots are all in the same tissue section. If expression distributions differ across groups of spots, unrestricted shuffling can create a reference distribution for the wrong null hypothesis and produce misleading p-values.
Let \(y=(y_1,\ldots,y_n)\) be expression measurements for one gene at \(n\) spots, and let \(W=(w_{ij})\) be a spatial weight matrix built from their locations. A test statistic \(T(y,W)\) summarizes the spatial pattern; for example, it could be Moran’s \(I\), whose interpretation and calculation were covered in the earlier material on spatial autocorrelation. A permutation scheme specifies a set \(G\) of allowed rearrangements of the spot labels. For each \(g\in G\), calculate \(T(g y,W)\), keeping the graph fixed if it was specified independently of expression.
The null distribution is generated by the allowed rearrangements, not by the word “permutation” alone. Unrestricted permutations use all \(n!\) arrangements. Restricted permutations might only rearrange values within prespecified blocks. If the null does not make the spots exchangeable under the chosen set of rearrangements, the resulting reference distribution is not justified.
Exact Permutation P-Values
For a one-sided test in which larger values of \(T\) are more extreme, an exact permutation p-value is the proportion of allowed arrangements whose statistic is at least as large as the observed statistic. For a two-sided test, extremeness must be defined in advance; a common choice for a statistic centered at zero is absolute magnitude. The observed arrangement is included in the reference set. Including ties makes the test conservative when the statistic has a discrete distribution.
This calculation is exact conditional on the observed values and fixed design information when the null makes all arrangements in \(G\) equally likely. For a two-sided test using absolute magnitude, replace the comparison by \(|T(g y,W)|\geq |T(y,W)|\). The choice of tail is part of the scientific hypothesis, not something to select after seeing which p-value is smaller.
Worked Example: An Exact Test on a Four-Spot Chain
Suppose a gene has hypothetical expression values \(y=(1,1,3,3)\) at four spots arranged in a chain, with undirected edges between spots 1–2, 2–3, and 3–4. Use the Moran statistic with symmetric binary weights, and test for positive spatial autocorrelation. Assume, for this illustration, that under the null the four spot values are exchangeable and the graph was fixed from the spot locations.
The mean is \(\bar{y}=2\), so the centered values are \(z=(-1,-1,1,1)\) and \(\sum_i z_i^2=4\). The weight sum is \(S_0=6\), because each of the three undirected edges contributes two directed weights. The directed cross-product sum is \((-1)(-1)+(-1)(-1)+(-1)(1)+(-1)(1)+(1)(1)+(1)(1)=2\). Thus \(I=(4/6)(2/4)=1/3\).
There are \(\binom{4}{2}=6\) distinct assignments of two values equal to 1 and two equal to 3. The corresponding centered sign sequences are \(++--\), \(--++\), \(+--+\), \(-++-\), \(+-+-\), and \(-+-+\). Their Moran statistics are, respectively, \(1/3,1/3,-1/3,-1/3,-1,-1\). Only the first two are at least as large as the observed \(1/3\).
Therefore the exact upper-tail p-value is \(2/6=0.3333\). At a significance level of \(\alpha=0.05\), this small hypothetical example does not provide evidence against the exchangeable-assignment null. The result does not establish that the gene has no spatial pattern; with only six possible arrangements, the test has coarse resolution and limited power.
When Unrestricted Shuffling Is Invalid
Unrestricted shuffling asserts a strong null: every spot could have received every observed expression value without changing the joint distribution. That assertion can fail if spots have different distributions for reasons allowed under the scientific null. For instance, if spots fall into prespecified tissue groups with different expression distributions, unrestricted shuffling moves values between groups. It then tests whether the entire observed map is spatially arranged, not whether there is spatial structure beyond those group differences.
Worked Example: A Small P-Value for the Wrong Null
Consider eight hypothetical spots in a chain. Spots 1–4 are in one prespecified tissue group and spots 5–8 in another. A gene has values \(0,0,0,0,1,1,1,1\). Suppose the question is whether there is additional spatial pattern beyond the group-specific distributions, so values may only be permuted within their own group under the null.
If values are coded as centered signs \(-1\) for 0 and \(+1\) for 1, the observed sequence has six matching adjacent pairs and one unlike pair. The undirected adjacent-product sum is \(6-1=5\). For the eight-spot chain, \(n=8\), \(S_0=14\), and \(\sum_i z_i^2=8\), so \(I=(8/14)(10/8)=5/7\), where 10 is the directed cross-product sum.
Under unrestricted shuffling there are \(\binom{8}{4}=70\) distinct assignments. Only two assignments put the four low values together and the four high values together in one run each, giving an upper-tail statistic at least as large as \(5/7\). The unrestricted p-value is \(2/70=0.02857\). But this is a test of unrestricted spatial assignment, not the stated null that allows the two groups to have different distributions. Within-group permutations leave these tied values unchanged, giving no evidence against that conditional null. The unrestricted p-value cannot be interpreted as evidence for additional within-group spatial structure.
The example also exposes a limitation: with no within-group variation, these data cannot reveal a finer spatial pattern within either group. A restricted permutation cannot manufacture information absent from the observations. The appropriate response is to recognize the target is not identifiable from this toy dataset, rather than to treat the unrestricted p-value as a substitute.
The same reasoning applies when choosing a permutation scheme for a more complex statistic. A restricted set of rearrangements is appropriate only when the restriction corresponds to the null and its exchangeability assumptions. Conversely, restrictions cannot be improvised after inspecting the observed map to obtain a preferred p-value. The groups, blocks, or other design constraints should be justified independently of the statistic being tested.
Monte Carlo Permutations and Residuals
When the allowed set is too large to enumerate, draw \(B\) random allowed permutations and calculate their statistics. If \(b\) simulated statistics are at least as extreme as the observed statistic, use the plus-one estimate \((b+1)/(B+1)\). The added one accounts for the observed arrangement and prevents a reported p-value of zero. This is a Monte Carlo approximation, not an exact enumeration of the full reference distribution.
Worked Example: A Monte Carlo Upper-Tail P-Value
Suppose a spatial gene test has observed statistic \(T_{\mathrm{obs}}=0.42\). Under a justified permutation scheme, \(B=999\) random rearrangements are generated, and 23 yield statistics at least 0.42. Assume the graph and allowed rearrangements were specified independently of the observed statistic.
The plus-one estimate is \((b+1)/(B+1)=(23+1)/(999+1)=24/1000=0.02400\). Thus, under the specified null and permutation scheme, the estimated upper-tail probability of a statistic at least this large is 0.024. It is not the probability that the null is true. With \(B=999\), the smallest reportable plus-one value is \(1/1000\); a value below that cannot be resolved by this number of simulations.
If this result is near a decision threshold, increase \(B\) to reduce Monte Carlo uncertainty. Also inspect the simulated statistics: a p-value calculation is not trustworthy if the permutation generator accidentally violates the intended restrictions or omits valid arrangements in a biased way.
A different situation arises when the statistic is based on a regression model that includes nonspatial terms. One may consider permuting residuals from a null model, then refitting the alternative model and recalculating the statistic. This is not automatically an exact test: fitted residuals are generally dependent and can have unequal variances even when the unobserved errors are exchangeable. Residual permutation is defensible only with conditions or a method that accounts for these features. In particular, “permute the residuals” is not a general remedy for nonexchangeable raw expression values.
Diagnostics, Alternatives, and Limitations
Before interpreting a permutation p-value, check the assumptions and implementation that produced it. Confirm that the graph was defined from locations rather than selected using the expression pattern being tested, or that any expression-dependent graph construction is repeated as part of each rearrangement. Check whether the spot values could plausibly be exchangeable under the null. Look for prespecified groups or blocks with distinct measurement processes or distributions. If these features make unrestricted exchangeability implausible, use a null model and permutation set that preserve the relevant structure, or use a model-based calibration whose assumptions can be assessed.
A useful diagnostic is to compare the observed statistic with the full permutation distribution and inspect its shape, ties, and attainable range. A very small number of distinct values indicates coarse p-value resolution. For Monte Carlo tests, record \(B\), the number of exceedances, the extremeness rule, and whether the observed arrangement was included through the plus-one calculation. These checks can reveal coding errors, but a well-shaped distribution does not prove that the exchangeability assumption holds.
Permutation calibration is often attractive because it can accommodate a statistic whose analytic null distribution is inconvenient. It does not remove the need to define the null, account for dependence or design structure, or choose a meaningful statistic. Model-based tests instead rely on a specified distribution for expression or model errors; when that model is credible, it can represent features that unrestricted shuffling ignores. Neither approach is automatically superior: permutation tests need a valid rearrangement mechanism, while model-based tests need a suitable model.
A permutation test also does not by itself address multiplicity across many genes, guarantee good power, or make an association causal. Its p-value describes extremeness under a particular null conditional on the design and data features held fixed. If those features do not match the scientific question, numerical precision cannot rescue the interpretation.
A Practical Calibration Workflow
State what spatial pattern is being tested and how the statistic measures it, including the direction or two-sided extremeness rule.
Identify which spot values or labels may be rearranged under the null, and whether any blocks or restrictions must be preserved.
Enumerate allowed rearrangements when feasible; otherwise draw random allowed permutations and retain the observed arrangement in the p-value calculation.
Review the permutation distribution and describe the assumptions, number of permutations, tail rule, and null to which the p-value refers.
Check Your Understanding
Answer each question before reading the solutions.
- What assumption permits an exact unrestricted permutation test of expression across spots?
- In an exact test with 40 allowed arrangements, 3 statistics are at least as extreme as the observed statistic. What is the p-value?
- Why can shuffling expression values across two prespecified tissue groups test the wrong null?
- In a Monte Carlo test with \(B=1999\) and \(b=9\), what plus-one p-value should be reported?
- Why does permuting fitted residuals not automatically give an exact test?
Solutions. 1. Under the null, the spot values must be exchangeable across all spots: every allowed arrangement must have the same probability conditional on what is held fixed. 2. The exact p-value is \(3/40=0.07500\), using the stated inclusive tail count. 3. Unrestricted shuffling moves values between groups and assumes exchangeability across them; if the null allows their distributions to differ, that assumption fails and the test addresses a stronger, different null. 4. The estimate is \((9+1)/(1999+1)=10/2000=0.005000\). 5. Fitted residuals can be dependent and have unequal variances because they are estimated using the data, so their rearrangements need not preserve the null distribution.