Swap and fill algorithms in null model analysis: rethinking the knight's tour.

Community assembly rules are often inferred from patterns in presence-absence matrices. A challenging problem in the analysis of presence-absence matrices has been to devise a null model algorithm to produce random matrices with fixed row and column sums. Previous studies by Roberts and Stone [(1990) Oecologia 83:560-567] and Manly [(1995) Ecology 76:1109-1115] used a "Sequential Swap" algorithm in which submatrices are repeatedly swapped to produce null matrices. Sanderson et al. [(1998) Oecologia 116:275-283] introduced a "Knight's Tour" algorithm that fills an empty matrix one cell at a time. In an analysis of the presence-absence matrix for birds of the Vanuatu islands, Sanderson et al. obtained different results from Roberts and Stone and concluded that "results from previous studies are generally flawed". However, Sanderson et al. did not investigate the statistical properties of their algorithm. Using simple probability calculations, we demonstrate that their Knight's Tour is biased and does not sample all unique matrices with equal frequency. The bias in the Knight's Tour arises because the algorithm samples exhaustively at each step before retreating in sequence. We introduce an unbiased Random Knight's Tour that tests only a small number of cells and retreats by removing a filled cell from anywhere in the matrix. This algorithm appears to sample unique matrices with equal frequency. The Random Knight's Tour and Sequential Swap algorithms generate very similar results for the large Vanuatu matrix, and for other presence-absence matrices we tested. As a further test of the Sequential Swap, we constructed a set of 100 random matrices derived from the Vanuatu matrix, analyzed them with the Sequential Swap, and found no evidence that the algorithm is prone to Type I errors (rejecting the null hypothesis too frequently). These results support the original conclusions of Roberts and Stone and are consistent with Gotelli's [(2000) Ecology 81:2606-2621] Type I and Type II error tests for the Sequential Swap. In summary, Sanderson et al.'s Knight's Tourgenerates large variances and does not sample matrices equiprobably. In contrast, the Sequential Swap generates results that are very similar to those of an unbiased Random Knight's Tour, and is not overly prone to Type I or Type II errors. We suggest that the statistical properties of proposed null model algorithms be examined carefully, and that their performance judged by comparisons with artificial data sets of known structure. In this way, Type I and Type II error frequencies can be quantified, and different algorithms and indices can be compared meaningfully.