Restricted Permutations for Paired and Blocked Designs in Genomic Data

Why Restrict the Permutations?

In genomic experiments, outcomes may be measured across many features, but treatment assignment often follows a design with structure: samples are paired, or units are grouped into blocks before treatment is assigned. A permutation test must respect that structure. If outcomes are exchangeable only within pairs or blocks, shuffling treatment labels across the entire experiment creates assignments that the design could not have produced and may compare units that are not exchangeable under the null.

The key task is therefore to specify the set of treatment assignments allowed by the design, and then calculate the reference distribution using only that set. The earlier material on exchangeability and exact permutation tests gives the general principle: under the null, the data distribution must be invariant under the transformations used to generate the reference distribution. Here, the transformations are restricted by the pairing or blocking structure.

Paired Designs: Swap Labels Within Each Pair

Suppose each pair contains two units, one assigned treatment and one assigned control. Under a sharp null hypothesis that treatment has no effect on any unit, the two outcomes within a pair would be unchanged if their treatment labels were swapped. If treatment was randomized within each pair with equal probability, the two labelings are equally likely. Thus, for each pair, the treatment-minus-control difference can either retain its observed sign or have its sign reversed.

For \(n\) independent pairs, there are \(2^n\) possible within-pair swap patterns. For a single genomic feature, let \(d_i\) denote the observed treatment-minus-control difference for pair \(i\). A natural statistic is the mean paired difference, \(\bar{d}=n^{-1}\sum_{i=1}^n d_i\). Under the restricted scheme, each reference value is \(\bar{d}^*=n^{-1}\sum_{i=1}^n s_i d_i\), where each \(s_i\) is either \(+1\) or \(-1\). This sign-flip interpretation requires the pairwise label swaps to be permitted by the design. It is not a general license to flip signs whenever data happen to be paired.

Blocked Designs: Preserve the Allocation Within Every Block

A block may contain more than two units. If the design assigns \(m_b\) of the \(N_b\) units in block \(b\) to treatment, the allowed assignments must keep exactly \(m_b\) treated units in that block. Under uniform random allocation subject to these counts, there are \(\binom{N_b}{m_b}\) allowed allocations for block \(b\). If blocks are randomized independently, the total number of assignments is the product of these counts across blocks.

A useful statistic should reflect the comparison intended by the design. One option is to calculate a treatment-control contrast within each block and then average those contrasts, giving each block equal weight. Another option may weight blocks according to their sizes or a prespecified analysis plan. The choice affects the statistic, not the allowed assignments: every reference value must still be calculated using the same statistic and the design-permitted treatment allocations.

Validity: Randomization and Exchangeability Are Not the Same Claim

In a randomized experiment, exactness can follow from the assignment mechanism. Under the sharp null, each unit's outcome is fixed regardless of its treatment label. If the design chooses uniformly from the allowed assignments, the observed assignment is uniform over that set under the null. Counting assignments at least as extreme as the observed one therefore gives an exact randomization p-value (with the usual conservative handling of ties).

In observational or model-based settings, there may be no treatment randomization. A permutation test then needs a distributional assumption: conditional on the blocks and the null, the outcomes must be exchangeable under the particular within-block rearrangements. Exchangeability means that applying any permitted rearrangement leaves the joint null distribution unchanged. Merely having matched samples does not guarantee this condition. Differences in variances, time trends, batch effects, or unmodeled structure can make within-group rearrangements invalid.

There is also a distinction between a sharp null and a weaker null such as zero average treatment effect. A sharp null specifies no effect for every unit and permits the randomization argument above directly. A null about only an average effect does not, by itself, fix every unit's unobserved outcome under the alternative assignment. A permutation test based on the sharp-null reference distribution should not automatically be described as exact for every weaker null.

Respect the Actual Assignment Probabilities

Not every restricted design assigns all permissible arrangements with equal probability. For instance, a paired trial might favor one orientation in each pair. In that case, counting every assignment once gives the wrong reference distribution. The correct randomization distribution weights each assignment by its probability under the actual design. This principle also applies when blocks are randomized with unequal probabilities or when some assignments are prohibited.

Multiple Features, Diagnostics, and Alternatives

When testing many genomic features, the design restriction applies to the sample labels, not separately to each feature. For a given allowed assignment, apply the same within-pair swaps or within-block allocation to all features. This preserves the feature-by-feature dependence induced by measuring the same samples across the genomic panel. Separate feature-wise tests can then use the resulting marginal reference distributions; constructing a joint multiple-testing procedure is a separate step.

Before trusting a restricted test, verify the design record: identify the pairs or blocks, confirm the treatment counts, and check whether assignments were uniform or weighted. Confirm that the statistic is recomputed after each allowed assignment and that no unit crosses a design-defined boundary. In model-based applications, examine whether important patterns remain within blocks under the null. Strong batch trends, heterogeneous variability, or pairwise differences driven by time order can undermine an exchangeability argument even when the code preserves pair membership.

A common mistake is to say, “The samples are related, so I will shuffle all treatment labels and then account for pairing in the statistic.” A paired statistic does not repair an invalid reference set: global shuffling can break pairs and generate assignments unavailable under the design. The correction is to define the allowable assignments first and compute the statistic only over those assignments.

Restricted permutation is attractive because it can give an exact test under a known randomization scheme without requiring a parametric outcome distribution. Its limitations are equally important: small numbers of pairs or blocks produce few distinct assignments and coarse p-values; validity depends on the sharp null for the randomization argument or exchangeability for a model-based argument; and a poorly chosen statistic may have low power for the effect pattern of interest. Model-based analyses can be useful when covariates or unequal variances matter, but they rely on their own assumptions. Residual permutation with nuisance covariates requires separate conditions and is not obtained merely by adding covariates to this label-shuffling procedure.