  Permutation tests are amongst the most commonly used statistical tools in
modern genomic research, a process by which p-values are attached to a test
statistic by randomly permuting the sample or gene labels. Yet permutation
p-values published in the genomic literature are often computed incorrectly,
understated by about 1/m, where m is the number of permutations. The same is
often true in the more general situation when Monte Carlo simulation is used to
assign p-values. Although the p-value understatement is usually small in
absolute terms, the implications can be serious in a multiple testing context.
The understatement arises from the intuitive but mistaken idea of using
permutation to estimate the tail probability of the test statistic. We argue
instead that permutation should be viewed as generating an exact discrete null
distribution. The relevant literature, some of which is likely to have been
relatively inaccessible to the genomic community, is reviewed and summarized. A
computation strategy is developed for exact p-values when permutations are
randomly drawn. The strategy is valid for any number of permutations and
samples. Some simple recommendations are made for the implementation of
permutation tests in practice.
