DETECTING genetic differentiation of subpopulations is an important problem in several areas of population biology, including areas of evolutionary genetics, ecology, and conservation biology. When data are obtained from two or more localities in the form of allele frequencies at one or more unlinked loci, standard chi-square tests (or likelihood-ratio tests) of homogeneity are appropriate (Workman and Niswander 1970) and can be quite powerful for detecting differentiation. Even when the expected counts in some cells are small, permutation methods can be utilized to give good results (Lewontin and Felsenstein 1965; Roff and Bentzen 1989). If the data consist of DNA sequences, or haplotyping at two or more linked sites, the same methods can be employed, if distinct sequences or haplotypes are treated as alleles. However, if the haplotype diversity is very high and the sample sizes are small, most haplotypes may appear in the sample only once and the methods based on haplotype frequencies will have low power and, in extreme cases, can become completely useless. Using these methods, longer sequences, which must contain more information, can result in lower power than short sequences. This problem is most severe with small samples and long sequences. To handle these kinds of data, Hudson et al. (1992) proposed the use of sequence-based statistics in the permutation tests. These sequence-based statistics utilize information on the numbers of differences between haplotypes and not just the frequencies of the haplotypes. The particular sequence-based statistics considered by Hudson et al. (1992) were shown to be more powerful than the chi-square statistic when haplotype diversity was very high, but were found to be relatively weak when the diversity was low. Thus, for low diversity samples, the chi-square statistic (or a likelihood-ratio statistic) would appear to be best, but, for high diversity samples, the sequence-based statistics should be used. Unfortunately, there are no absolute criteria known for when the chisquare statistic should be employed and when the sequence-based statistics should be used. It would be desirable to have a single statistic that performs well at all levels of diversity. In this note, a new sequence-based statistic is introduced that appears to have this property. Under a symmetric two-island model with mutations occurring according to the infinite-sites model, this new statistic is found to be as powerful or more powerful than other statistics that have been proposed for detecting genetic differentiation. This superior power is found over a wide range of haplotype diversity.

The new statistic, referred to as the nearest-neighbor statistic (S_nn), is a measure of how often the “nearest neighbors” (in sequence space) of sequences are from the same locality in geographic space. This is made more precise below. The statistic is applicable when genetic data are collected on individuals sampled from two or more localities. It is assumed that haplotypic data are obtained, either in the form of DNA sequences or data on many tightly linked markers.

To define S_nn, it is helpful to first establish some notation. For concreteness, suppose the data collected are mitochondrial sequences obtained from n individuals, some of which are from locality 1 and some from locality 2. (The statistic automatically generalizes to more localities.) We assume all sequences are the same length with no gaps. Arbitrarily number the individuals from 1 to n, and denote the sequence of individual i by s_i. Let d_ij equal the number of nucleotide sites at which s_i differs from s_j. Focus on a particular individual, say, individual k, and let m_k denote the minimum of {d_kj}, j = 1, 2, … , k − 1, k + 1, … , n. Thus, m_k is the distance to the nearest neighbor(s) of individual k. (Neighbor here reflects closeness in sequence space, not in geographic space.) Let T_k equal the number of individuals for which d_kj = m_k, again for fixed k and j ≠ k. T_k is the number of nearest neighbors of individual k. And let W_k equal the number of individuals with d_kj = m_k, that are from the same locality as individual k. In other words, W_k is the number of nearest neighbors to individual k that are from the same locality as individual k. Now define X_k = W_k/T_k. Thus, X_k is the fraction of nearest neighbors of individual k that are from the same locality as individual k. Thus, if individual k has only a single nearest neighbor, then X_k is one if the nearest neighbor is from the same locality as individual k, and X_k is zero if the nearest neighbor is from a different locality. The statistic S_nn is simply the average of the X_k: Snn=Σj=1nXj∕n. S_nn is a measure of how often the nearest neighbors of sequences are found in the same locality. If a population is strongly structured, one expects to find the nearest neighbor of a sequence in the same locality. Thus, S_nn is expected to be near one when the populations at the two localities are highly differentiated and near one-half when the populations at the two localities are part of the same panmictic population (and sample sizes from the two localities are equal). To assess whether S_nn is significantly large for a particular sample (indicating that the populations at the two localities are differentiated), the usual permutation scheme is applied to estimate a P value. Specifically, a permutation consists of randomly reassigning sequences to localities, so that the number of sequences from each locality is always the same as in the original sample. The proportion of permuted samples with S_nn larger than or equal to the observed value is the estimated P value.

To assess the power of permutation tests using S_nn to detect geographic differentiation, the same symmetric two-island model considered by Hudson et al. (1992) was used. The parameters of this model are N, the island population size, u, the neutral mutation rate, c, the recombination rate between the ends of the segment sequenced, and m, the migration fraction per generation. An infinite-sites model was assumed (and thus no recurrent mutations occur in these simulations.) The results of these simulations are shown in Tables 1 and 2. Table 1 shows the results for all parameter values and sample sizes considered by Hudson et al. (1992). In Table 2, more results for small sample sizes are given. For comparison, the power of the permutation tests based on the chi-square statistic (χ²) and on K_S*, Z*, and H_S are also shown in the tables. The statistics K_S*, Z*, and H_S were the most powerful sequence-based statistics found by Hudson et al. (1992).

In Table 1, we find that S_nn has equal or higher power than the χ² statistic in all cases except one. (The exception is the first case in Table 1 in which the power of S_nn was 0.77 while the power of χ² was 0.78, a very small difference.) For most cases in this table, S_nn has equal or only slightly higher power than the test based on χ². However, in cases with small sample sizes (n₁ = n₂ = 10 or 15), especially with recombination, there is substantially higher power with the S_nn statistic. (In the case with n₁ = n₂ = 10 and 4Nc = 20, the power with S_nn is 0.46, while the power with χ² is 0.21.) These results motivated us to look at more cases with small sample size, which are shown in Table 2.

For samples of size 6 from each locality, the S_nn statistic is substantially more powerful than the χ² statistic at all levels of variation examined (see Table 2). For samples of size 10 from each locality, S_nn is only slightly more powerful than χ² at low levels of variation, but at higher levels of variation, S_nn has very much higher power than χ². In contrast to the chi-square statistic, higher mutation rates (longer sequences) always lead to more power using the nearest-neighbor statistic, which accords with the intuition that longer sequences should provide more information. With low to moderate levels of variation, the S_nn statistic is more powerful than the sequence-based statistics of Hudson et al. However, with the small sample sizes considered in Table 2, it appears that K_S* and Z* may have slightly higher power than S_nn when levels of variation are very high. (See the case n₁ = n₂ = 6 and 4Nu = 4Nc = 10.)

Summarizing, we find that among the statistics tested, S_nn is the most powerful statistic, or nearly as powerful as the best statistic, under all conditions examined. It should be emphasized, however, that all assessments of power were carried out with a symmetric two-island model and assuming that mutations occur according to an infinite-sites model (in which no multiple hits occur). Other models may lead to different conclusions. The use of S_nn eliminates the need to establish criteria for when to use an “allele” frequency-based statistic and when to use a sequence-based statistic. This statistic may also be of use in testing for genetic differences between samples in case-control studies, though these usually consist of diploid data in large samples.

Source code (in the language C) for a program that carries out the test on Unix or Linux machines is in a file, snn.c, available at http://home.uchicago.edu/~rhudson1.

• Received February 15, 2000.
• Accepted May 1, 2000.

• Copyright © 2000 by the Genetics Society of America