Permutation Testing Methodology

Permutation testing consists of running many tests which are just like the original test except that the dependent variable is permuted differently for each test, and counting the number of times the test statistic resulting from a permuted dependent variable is more significant than the statistic from the original test.

The permuted p-value is the fraction of permuted tests which are more significant than or as significant as the original test (this is the definition of a p-value). The original test is counted as one of the “permuted tests” in this calculation. This is meant to approximate the probability that the test could come out as “positive” by chance alone.

Note

The permutations that are used are not based on a time of day seed, but on a constant seed. This means that permutation results will be identical when the study is re-run.

Single Value Permutations

With single value permutations, the dependent variable is permuted and the given statistical test is performed using the given model on the given marker or predictor. The permutation methodology is the same for genotypic association tests and numerical association tests. The independent variables in the first case are genetic markers, and in the second numerical predictors. In this paragraph and those following, “marker” can be replaced with “predictor” depending on the context of the permutation testing. Only “marker” will be used for simplicity.

This process is repeated the number of times you select. The permuted p-value is defined as the fraction of times a test with a permuted dependent variable on the given marker came out as significant as or more significant than the same test on the same marker with the non-permuted dependent variable.

Note

This single-value permutation technique focuses exclusively on the marker in question, and by itself does not offer any type of correction for multiple testing.

Single Value Permutation Example

Suppose your approximated p-value (based on a chi-square distribution) is 0.2, you are performing 10 permutations, and the significance of those permutations (based on the same chi-square distribution) may be expressed as the following approximated p-values (counting the original test as the first “permutation”):

0.20
0.15
0.09
0.51
0.31
0.01
0.26
0.11
0.05
0.18

In the above column, there are 7 outcomes where the approximated p-value is equal to or less than 0.2. The permuted p-value is therefore

\frac{7}{10}=0.7

Full Scan Permutations

The full-scan permutation technique differs from the single-value technique in that it addresses the multiple-testing problem. It does this by comparing the original test result from an individual marker not merely with the permuted result from that marker, but also with the permuted results from all the rest of the markers. If any of these comparisons comes out to be more significant than the unpermuted result of the marker in question, the permutation is considered to have resulted in the “permuted test being more significant than the unpermuted test”.

To be specific, the following procedure is used for full-scan permutation testing:

  1. For the number of times you have specified, the dependent variable is permuted and the test is performed over all markers. From each permutation, the most significant results from any of the markers are kept track of.
  2. The full-scan permuted p-value of each marker may now be found. It is the fraction of permutations for which the most significant result over all markers for that permutation was as significant as or more significant than the test on the marker in question using the non-permuted dependent variable.

Note

This procedure will tend to multiply the result by a value somewhat equal to the number of markers being tested, and thus gives answers comparable to those from Bonferroni-corrected p-values.

Full Scan Example One

You run the same association test on four spreadsheets. These spreadsheets are all alike, except that one has the real data that you are interested in, and the other three have the same data except that the dependent variable has been permuted randomly in those spreadsheets.

You look at the (approximated) p-values from all of these tests, and note that the best approximated p-value from the first spreadsheet on any marker (which came from marker 4) is 0.0003. You also note that the best approximated p-values (which resulted from various markers) from the second, third, and fourth spreadsheets are 0.005, 0.02, and 0.013.

Using this technique, you could say that the full-scan permuted p-value of marker 4 would be one (the number of spreadsheets whose significance measured as a p-value was 0.0003 or better) divided by four (the total number of spreadsheets), or 0.25.

Normally, to get a better idea of the real p-value, you would perform many more permutations than this! For instance, one thousand permutations or more would be necessary to more accurately gage a p-value near 0.001.

Full Scan Example Two

Suppose you have 5 markers, and their approximated test p-values (based on a chi-square distribution) are:

0.20 0.10 0.02 0.34 0.52

Their Bonferroni-corrected p-values would be:

1.00 0.50 0.10 1.00 1.00

Also suppose we do full-scan permutation testing using 10 permutations on these markers, and the approximated p-value results of those permutations on those markers (based on the same chi-square distribution and counting the original test as a “permutation”) are:

0.20  0.10  0.02  0.34  0.52
0.15  0.13  0.71  0.05  0.26
0.09  0.17  0.41  0.26  0.22
0.51  0.36  0.47  0.92  0.01
0.20  0.74  0.26  0.87  0.23
0.01  0.46  0.21  0.08  0.05
0.26  0.61  0.92  0.37  0.43
0.11  0.54  0.29  0.08  0.13
0.05  0.06  0.04  0.39  0.42
0.18  0.69  0.21  0.19  0.14

In the above data, we find the following best permuted-test outcomes over all markers for each of the permutations are:

0.02 (from the third marker)
0.05 (from the fourth marker)
0.09 (first marker)
0.01 (fifth marker)
0.20 (first marker)
0.01 (first marker)
0.26 (first marker)
0.08 (fourth marker)
0.04 (third marker)
0.14 (fifth marker)

For the first marker, whose approximated p-value from actual data was 0.20, we find that the best approximated p-values from the permutations other than permutation 7 (0.26) were all as good as or as better than 0.20. Thus the full scan permuted p-value for the first marker is 9/10 or 0.90.

For the second marker, at 0.10, all permutations except permutation 5 (0.20), permutation 7 (0.26), and permutation 10 (0.14) were better than its actual data value. Thus, its full-scan permuted p-value is 7/10 or 0.70.

The third marker has an approximated p-value of 0.02 on actual data, which is much better than that for the other markers, and is only equaled or bettered by itself (“permutation” 1 at 0.02), permutation 4 (0.01) and permutation 6 (0.01). Thus, its full-scan permuted p-value is 3/10 or 0.30.

Meanwhile, every permutation had a better approximated p-value than either the 0.34 or 0.52 values from the last two markers. Thus, these markers both have a full-scan permuted p-value of 10/10 or 1.00.

Comparing the full-scan permuted p-values for every marker with its Bonferroni-corrected p-value for real data we get these similar values:

0.90  0.70  0.30  1.00  1.00
1.00  0.50  0.10  1.00  1.00

Full Scan Example Three

Let’s say your full-scan permuted p-value was 0.463 from when you performed 1000 permutations. This means that of the 1000 permutations performed, the p-value from the internally saved list of the best statistical results from the permutations was better 463 times out of 1000. This would be a poor showing. However, you must take into consideration that each time the permutation was performed, it did not do anything like averaging the approximated p-values for all the markers, but it took the one marker with the best showing (whose approximated p-value would be the lowest).