Donor-Restricted Permutation Tests

Why Permute Donor Labels?

In a single-cell study, a condition may be measured in thousands of cells but represented by only a modest number of independent donors. If the scientific question concerns a difference between conditions across donors, the permutation procedure must reflect that sampling structure. The relevant units to reassign are the donors, not the cells within them.

A donor-restricted permutation test compares the observed group difference with the differences that could arise under other allowed assignments of group labels to the same donor-level summaries. It can provide an exact test when the assignment mechanism or a suitable exchangeability assumption makes those assignments equally plausible under the null. It does not make a small donor sample large, nor does it remove the need to specify the null hypothesis and design.

What Makes a Permutation Test Valid?

Let \(Y_i\) be a prespecified summary for donor \(i\), and let \(G_i\) be that donor's group label. For example, \(Y_i\) might be the mean expression of a gene among the donor's cells in a defined cell type. The summary should be computed by the same rule for every donor, and the analysis should use one row per donor. A common statistic for two groups is the difference in donor means:

The permutation test holds the observed donor summaries fixed and rearranges the group labels according to the study's assignment scheme. If group A has \(n_A\) donors and group B has \(n_B\), with \(n=n_A+n_B\), an unrestricted two-group allocation permits \(\binom{n}{n_A}\) assignments of the A label. The B label is assigned to the remaining donors. In this setting, the possible values of the statistic form the permutation distribution.

The validity condition is about assignments, not merely about having a numerical statistic. In a randomized study, the test is exact for a sharp null of no treatment effect on any donor if the permutations reproduce the actual randomization scheme. In an observational comparison, exactness instead requires that, under the null, donor outcomes be exchangeable with respect to the group labels, conditional on the restrictions used. For a simple unrestricted test, this means that the donor-level outcomes have the same distribution across groups under the null. Equality of group means alone does not generally imply exchangeability; groups could have different variances or shapes while sharing a mean.

Donors must be independent sampling units for the intended inference, and the allowed permutations must preserve relevant design features. If assignment was constrained, or if valid randomization was conducted within strata, the permutation scheme must preserve those constraints. Shuffling every label freely when the design did not allow that assignment does not reproduce the null distribution. Technical replicates or multiple samples from one donor do not become independent donors simply because they appear as separate rows.

Exact P-Values and Their Justification

For a two-sided test using a statistic where larger absolute values indicate stronger disagreement with the null, the exact permutation p-value is the fraction of allowed assignments whose statistic is at least as extreme as the observed one. Ties count as at least as extreme. If \(\mathcal{A}\) is the set of allowed assignments and \(T(a)\) is the statistic under assignment \(a\), then:

The reason this calculation controls the test's type I error under the stated conditions is that, under the null, the observed assignment is uniformly distributed among the allowed assignments. The rank of its statistic within the permutation distribution is therefore itself determined by a uniform position, with ties handled conservatively by counting all equally extreme assignments. A test that rejects when this tail fraction is no greater than \(\alpha\) consequently has null rejection probability no greater than \(\alpha\). Because the number of assignments can be small, an exact test may have only a few attainable p-values.

A Larger Exact Test and the Resolution Limit

As the number of donors increases, the number of possible allocations can grow quickly. Even so, when it is manageable, enumerating every allowed allocation gives the exact permutation distribution and avoids Monte Carlo approximation. The smallest possible p-value depends on the number and structure of the permitted assignments; it is not determined by the number of cells.

Monte Carlo Permutations

If enumerating all allowed assignments is impractical, sample \(B\) assignments from the valid permutation scheme and recalculate the statistic for each. For a two-sided test, let \(b\) be the number of sampled statistics with absolute value at least \(|T_{\mathrm{obs}}|\). A commonly used finite-simulation estimate is:

The added one treats the observed assignment as part of the reference set and prevents a reported Monte Carlo p-value of zero. This is an approximation based on the sampled assignments, not a full enumeration. With too few draws, the estimate can vary noticeably from run to run, especially for small tail probabilities. Report \(B\), the tail-count rule, and whether the p-value was exact or Monte Carlo. Increasing \(B\) reduces simulation error but does not repair an invalid permutation scheme.

For example, if \(B=999\) assignments are sampled and \(b=39\) have an absolute statistic at least as large as the observed one, then \(\hat{p}_{\mathrm{MC}}=(39+1)/(999+1)=0.0400\). This estimate is based on the donor-level statistic and valid donor-level assignments; using many simulated rearrangements cannot compensate for having few independent donors.

Why Cell-Level Shuffling Fails

Cells from the same donor share biological and technical features, so their measurements are not generally independent draws from a common population of cells. Unrestricted cell-level shuffling breaks the donor clusters: it can assign cells from one donor to both conditions and creates arrangements that were not possible under a design in which condition was assigned or observed at the donor level. The resulting reference distribution answers a different question and may make uncertainty appear much smaller than the donor-level evidence supports.

Diagnostics, Alternatives, and Limits

Before interpreting a result, verify that the design and computation match the intended inference. Useful checks include:

• Confirm that each independent donor contributes one analysis unit, or that any repeated measurements are handled according to the design rather than counted as new donors.
• Check that the donor summary and cell-type definition were selected consistently across donors and were not changed after inspecting which choice produces the strongest result.
• Verify the group sizes and any assignment restrictions in every permutation. If only certain assignments were possible, exclude all others.
• Compare the observed statistic with the full or sampled permutation distribution. A reversed group coding should reverse the sign of a difference but leave a two-sided p-value unchanged.
• Check whether a few donors dominate the summaries. A permutation test does not protect against outliers, influential donors, measurement errors, or poor donor summaries.

A donor-level two-sample \(t\)-test is a parametric alternative for comparing group means; it relies on its own assumptions about the donor-level data and reference distribution. A donor bootstrap, covered in the earlier material on bootstrapping donors rather than cells, resamples independent donors to estimate uncertainty rather than rearranging labels to test a null. These approaches answer related but distinct inferential questions. A cell-level permutation is not an appropriate shortcut when the intended unit is the donor.

Permutation tests also have important limits. They do not eliminate confounding in an observational study: exchangeability may be implausible if donor group membership is associated with other causes of the outcome. A test of a sharp no-effect null is not, without additional assumptions, a confidence interval for the size of an effect. In particular, a small p-value is not the probability that the null is true, and a large p-value does not establish no effect. Report the donor-level effect estimate and its units alongside the p-value, and interpret both in light of the design and limited donor sample.