Why the Permutation Scheme Matters
A permutation test asks whether the observed association between batch and measured molecular values is unusually large relative to values obtained under a null arrangement. The key choice is not only the test statistic; it is which rearrangements are allowed. If biological groups differ and batch labels are shuffled across those groups, the shuffled data may break a real biological structure that should have been held fixed. The resulting reference distribution need not represent the null hypothesis of interest.
Blocking restricts the shuffling to samples that share specified cohort or biological characteristics. It can make a test more relevant to a conditional question, such as whether batch is associated with expression among samples of the same disease group. Blocking does not, by itself, solve confounding or make observational batch assignments exchangeable. The test is justified only when the permitted permutations match the assumptions of the null model.
Let sample \(i\) have a batch label \(B_i\), a block label \(S_i\), and a molecular outcome \(Y_i\), which may be a single feature or a vector of features. A permutation \(\pi\) is allowed only if it maps each sample to another sample in the same block: \(S_{\pi(i)}=S_i\). Applying the same permutation to the complete outcome vector for each sample retains dependence among features. It does not independently shuffle each feature, which would generally destroy cross-feature dependence.
Statistic and Permutation Reference Distribution
For a single feature, a useful statistic is a partial \(F\)-statistic from nested linear models. The reduced model includes block indicators and other prespecified nuisance covariates; the full model adds batch terms. Let \(RSS_0\) and \(RSS_1\) denote the residual sums of squares from the reduced and full models, respectively. If the full model adds \(q\) estimable batch parameters and has residual degrees of freedom \(df\), define
A large value indicates that batch terms explain additional variation after the included covariates. For a permutation test, recompute this statistic after each allowed reassignment of batch labels, fitting the same reduced and full model structure each time. The statistic need not follow an \(F\) distribution for the permutation ranking to be used, provided the exchangeability condition holds.
For a prespecified two-sided contrast, use an absolute statistic such as the absolute estimated batch coefficient. For several features, a global statistic might summarize the extra sum of squares across features. If the scientific claim concerns whether any of many features is associated with batch, a maximum statistic across features can be used; each permutation must use the same whole-sample label reassignment across features.
With \(M\) permitted assignments and \(T^{(m)}\) the statistic for assignment \(m\), the exact upper-tail p-value is
The observed assignment is included in the set of permitted assignments. When only a random sample of \(R\) permutations is drawn, a common Monte Carlo estimate is
The added one accounts for the observed arrangement and prevents a reported p-value of zero. Ties count in the upper tail. A small p-value is evidence against the specified conditional null under the permutation assumptions; it is not the probability that the null is true.
Constructing and Checking a Blocked Test
Specify the batch association being tested, the outcome or feature set, and a statistic sensitive to the association of interest. Decide whether the test is feature-specific or global.
Use strata that must remain fixed for the conditional question, such as disease group or cohort. Do not create blocks after inspecting which choice gives the smallest p-value.
Within each block, confirm that batch labels can vary and that the outcomes are plausibly exchangeable under the null. A block containing only one batch label contributes no label rearrangements.
Keep block membership fixed, rearrange batch labels only within blocks, and calculate the same statistic for each permitted assignment. Preserve each sample's entire feature vector.
State the statistic, blocks, number or sampling method of permutations, p-value, and key exchangeability limitations. Do not interpret a small p-value as evidence that batch caused the observed molecular differences.
Worked Calculations
Worked Example: Exact Test With Two Biological Blocks
Hypothetical data. A single feature is measured in two biological strata, with one sample from each of two batches in each stratum. The values are 2 and 5 in stratum 1, and 4 and 8 in stratum 2. Suppose the observed labels are A, B in that order within both strata. Test for a batch difference using the absolute batch coefficient in a model with stratum indicators and one batch indicator.
Within stratum 1, the B-minus-A difference is \(5-2=3\); within stratum 2 it is \(8-4=4\). With equal representation, the fitted batch coefficient is their average:
There are two possible label assignments within each stratum: keep or swap A and B. Thus there are \(2^2=4\) permitted assignments. The resulting B-minus-A differences by stratum are \((3,4)\), \((-3,4)\), \((3,-4)\), and \((-3,-4)\). Their average coefficients are \(3.5,\ 0.5,\ -0.5,\) and \(-3.5\). The absolute statistic is at least the observed \(3.5\) for two of the four assignments, so
The large observed difference is not unusual in this very small set of valid assignments. This conclusion assumes that, under the null, outcomes are exchangeable between the two batch labels within each stratum. The example also shows why a small number of blocks can give a coarse p-value.
Worked Example: Why Unrestricted Shuffling Can Mislead
Hypothetical data. Four samples in biological stratum L have feature value 0 and are all processed in batch A. Four samples in stratum H have feature value 10 and are all processed in batch B. The observed difference in batch means is \(10-0=10\). The strata differ biologically, but there is no within-stratum overlap in batch.
An unrestricted test would choose four of the eight values for a permuted batch A. There are \(\binom{8}{4}=70\) assignments. A difference in means with absolute value at least 10 occurs only when batch A receives all four zeros or all four tens, giving
That calculation treats every allocation of four labels across the eight samples as possible under the null, including allocations that mix the biological strata. It therefore uses a reference distribution that does not preserve the biological structure. Under the blocked scheme, neither stratum permits a label swap: every sample in L is A, and every sample in H is B. There is no within-stratum batch contrast to test. The appropriate conclusion is not that the blocked p-value is zero or nonsignificant; the conditional batch effect is not identifiable from these data. The unrestricted p-value cannot repair this lack of overlap.
Worked Example: Monte Carlo Test Across Multiple Features
Hypothetical analysis. Suppose 30 samples fall into three prespecified biological strata, each containing samples from both batches A and B. Two molecular features are tested. For each feature, fit the block-adjusted batch model and calculate the absolute \(t\)-statistic for its batch coefficient. Use the maximum of the two absolute statistics as the global statistic, so each permutation tests whether either feature is unusually associated with batch.
In the observed data, the absolute statistics are 3.10 and 2.40, so \(T_{\mathrm{obs}}=\max(3.10,2.40)=3.10\). In 999 randomly sampled permutations of batch labels within strata, 18 maximum statistics are at least 3.10. The Monte Carlo p-value is
Under the stated exchangeability assumption, this is evidence against the joint null that neither feature is associated with batch, conditional on the strata. The maximum is recalculated across both features for every permutation; this accounts for examining two features in this particular global test. The test does not establish that batch caused either feature difference, and the result depends on the chosen blocks and on the validity of within-block exchangeability.
Justification, Diagnostics, and Alternatives
The justification for an exact permutation test follows from symmetry. Under the null exchangeability condition, the observed arrangement and every allowed within-block rearrangement have the same conditional distribution. If the statistic is recomputed for each arrangement, the observed statistic's rank among the permitted statistics is therefore uniform apart from ties. Counting the arrangements with statistic at least as large as the observed one gives a valid upper-tail test; ties make the test conservative rather than anti-conservative.
The central diagnostic is the batch-by-block table. Look for blocks containing only one batch, very small numbers of samples in a batch, or a design in which nearly all batch variation is between rather than within blocks. Also check whether the blocks represent the biological structure relevant to the question. Unmeasured or omitted structure can still violate exchangeability. If distributions differ within blocks, a test of equal means may not justify unrestricted within-block label permutation, even when the means are equal.
A continuous covariate cannot generally be handled by making an exact block for every distinct value: that may leave no exchangeable samples. Possible alternatives include a prespecified regression model with that covariate, carefully justified residual-permutation methods, or a design-based procedure appropriate to how samples were assigned. These alternatives have their own assumptions. In particular, permuting raw labels within coarse groups does not automatically control a continuous confounder.
| Approach | What it preserves | Main caution |
|---|---|---|
| Unrestricted label permutation | Overall batch counts | Invalid when exchangeability holds only within biological or cohort strata |
| Blocked label permutation | Batch counts within each specified block | Requires within-block exchangeability and adequate overlap |
| Parametric regression test | Specified covariate structure through the model | Inference depends on model and error assumptions |
| Residual-permutation method | Some fitted nuisance structure, depending on the method | Validity is not automatic; residuals may not be exchangeable |
Blocked tests are useful when the conditional null and the exchangeability assumptions are defensible, but they have clear limits. Blocking cannot identify a batch effect perfectly confounded with cohort or biology; excessive blocking can leave too few permutations; and a small p-value does not measure the size or practical importance of a batch effect. Report effect estimates and units alongside test results when those quantities are relevant, and describe the design limits explicitly.
Common Pitfall
A common mistake is to argue, “The overall batch counts are preserved, so shuffling all labels is valid.” This is wrong when samples from different biological strata are not exchangeable under the null. The correction is to preserve the strata required by the conditional question and verify that batch labels actually vary within them. If the required restriction leaves no assignments, the data do not support that permutation test; the lack of overlap is a finding about the design, not a reason to relax the restriction until a test becomes possible.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- In a blocked test, what must remain unchanged when labels are permuted?
- A study has two blocks, each with two samples. In each block, the observed outcome values are 1 and 4, and one sample is labelled A and one B. The observed absolute mean difference is 3. How many assignments are permitted, and what is the exact two-sided p-value based on the absolute difference?
- Why does a block containing only batch A provide no within-block batch contrast?
- For 499 random permutations, 9 statistics are at least as large as the observed statistic. Calculate the Monte Carlo p-value using the plus-one formula.
- Does a valid blocked permutation test prove that batch caused the observed association? Explain.
Solutions. (1) Block membership stays fixed; batch labels are rearranged only among samples in the same block, preserving the batch counts in each block. (2) Each block has two label arrangements, so \(2^2=4\) assignments. The absolute difference is 3 when both block differences have the same sign, which occurs in 2 assignments; the other 2 assignments give a difference of 0. Thus \(p=2/4=0.50\). (3) Permuting labels within that block cannot change any label, so it contributes no variation in batch assignment and no information about a within-block contrast. (4) \(\hat{p}=(1+9)/(499+1)=10/500=0.020\). (5) No. The test evaluates evidence against a conditional null under exchangeability assumptions; an association can reflect other causes or residual confounding.