2.1 Nearest-neighbor projected-distance regression

Like other nearest-neighbor feature selection algorithms, the performance of NPDR depends on appropriate choice of neighborhood optimization criteria. The size of neighborhoods must be chosen appropriately for optimal detection of important statistical effects. It has been shown using simulations that neighborhood size should be as large as possible to optimally detect main effects, whereas smaller neighborhoods are necessary to detecting interactions [6]. NPDR allows for any neighborhood algorithm to be used, such as fixed or adaptive k, and fixed or adaptive radius. Especially in the case of radius methods, one needs some sense of central tendency with respect to pairwise distances between a given target instance and its neighbors. Similar to the radius problem, for fixed-k neighborhoods we need to choose k so that the average distance within neighborhoods is not too large or too small with respect to the empirical average pairwise distance between pairs of instances. In order for the appropriate choice of neighborhood size to be made, we need to know the central tendency and scale of the distance distribution generated on our data.

Although we do not use NPDR in the current study, it is an important motivation for derivations herein, so we briefly describe how NPDR computes importance scores for classification problems. In the case of dichotomous outcomes, NPDR estimates regression coefficients of the following model (3) where is the probability of instances being in different classes, β_a indicates the relative importance of attribute for predicting the binary outcome, and d_ij(a) is the attribute diff (Eq 2). The outcome of NPDR, modeled by , is the diff computed as a function of instance class labels, which is given by the following (4) where is the binary response (or outcome). The purpose of NPDR is ultimately testing the one-sided hypotheses given by (5) where rejecting the null hypothesis (H₀) implies that there is significant evidence to conclude that attribute is important for classification.

All derivations in the following sections are applicable to nearest-neighbor distance-based methods in general, which includes not only NPDR, but also Relief-based algorithms. Each of these methods uses a distance metric (Eq 1) to compute neighbors for each instance . Therefore, our derivations of asymptotic distance distributions are applicable to all methods that compute neighbors in order to weight features. The predictors used by NPDR (Eq 3), however, are the one-dimensional projected distances between two instances (Eq 2). Hence, all asymptotic estimates we derive for diff metrics (Eq 2) are particularly relevant to NPDR. Since the standard distance metric (Eq 1) is a function of the one-dimensional projection (Eq 2), asymptotic estimates derived for this projection (Eq 2) are implicitly relevant to older nearest-neighbor distance-based methods like Relief-based algorithms.

We proceed in the following section by applying the Classical Central Limit Theorem and the Delta Method to derive the limit distribution of pairwise distances on any data distribution that is induced by the standard distance metric (Eq 1). We assume independent samples in order to derive closed-form moment estimates and to show that distances are asymptotically normal. In real data, it is obviously not the case that samples or attributes will be independent; however, the normality assumption for distances is approximately satisfied in a large number of cases. For example, it has been shown using 100 real gene expression data sets from microarrays, that approximately 80% of the data sets are either approximately normal or log-normal in distribution [14]. We generated Manhattan distances (Eq 1, q = 1) on 99 of the same 100 gene expression data sets after applying a pre-processing pipeline. We excluded GSE67376 because this data included only a single sample. Before generating distance matrices, we transformed the data using quantile normalization, removed genes with high coefficient of variation, and standardized samples to have zero mean and unit variance.

We computed densities for each distance matrix, as well as quantile-quantile plots to visually assess normality (S26-S124 Figs in S1 File). The estimated densities and quantile-quantile plots indicate that most of the gene expression data sets yield approximately normally distributed distances between instances. Another example involves real resting-state fMRI data from a study of mood and anxiety disorders [15], where the data was generated both from a spherical ROI parcellation [16] and a graph theoretic parcellation [17]. The data consists of correlation matrices between ROI time series with respect to each parcellation and each subject. Each subject correlation matrix, excluding the diagonal entries, was vectorized and combined into a single matrix containing all subject ROI correlations. We then applied a Fisher r-to-z transformation and standardized samples to be zero mean and unit variance. The output of this process was two data matrices corresponding to each parcellation, respectively. Analogous to the gene expression microarray data, we computed Manhattan distance matrices for each of the two resting-state fMRI data sets. We generated quantile-quantile and density plots for each matrix (S125 and S126 Figs in S1 File). Both sets of pairwise distances were approximately normal.

2.2 Asymptotic normality of pairwise distances

Suppose that for two fixed and distinct instances and a fixed attribute . represents any data distribution with mean μ_X and variance .

It is clear that |X_ia − X_ja|^q = |d_ij(a)|^q is another random variable, so we let be the random variable such that (6)

Furthermore, the collection is a random sample of size p of mutually independent random variables. Hence, the sum of over all is asymptotically normal by the Classical Central Limit Theorem (CCLT). More explicitly, this implies that (7)

Consider the smooth function g(z) = z^1/q, which is continuously differentiable for z > 0. Assuming that , the Delta Method [18] can be applied to show that (8)

Therefore, the distance between two fixed, distinct instances i and j (Eq 1) is asymptotically normal. In particular, when q = 2, the distribution of asymptotically approaches . A unique characteristic inherent to the q = 2 case is the fact that we get not only an asymptotic estimate for the average second raw moment of the L_q metric (Eq 8, q = 2), but also the variance of the second raw moment. This leads to the following higher order estimate of the sample mean in the case of q = 2 (9)

The distribution of pairwise distances convergences quickly to a Gaussian for Euclidean (q = 2) and Manhattan (q = 1) metrics as the number of attributes p increases (Fig 1). We compute the distance between all pairs of instances in simulated datasets of uniformly distributed random data. We simulate data with fixed m = 100 instances, and, by varying the number of attributes (p = 10, 100, 10000), we observe rapid convergence to Gaussian. For p as low as 10 attributes, Gaussian is a good approximation. The number of attributes in bioinformatics data is typically quite large, at least on the order of 10³. The Shapiro-Wilk statistic approaches 1 more rapidly for the Euclidean than Manhattan, which may indicate more rapid convergence in the case of Euclidean. This may be partly due to Euclidean’s use of the square root, which is a common transformation of data in statistics.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Convergence to Gaussian for Manhattan and Euclidean distances for simulated standard uniform data with m = 100 instances and p = 10, 100, and 10000 attributes.

Convergence to Gaussian occurs rapidly with increasing p, and Gaussian is a good approximation for p as low as 10 attributes. The number of attributes in bioinformatics data is typically much larger, at least on the order of 10³. The Euclidean metric has stronger convergence to normal than Manhattan. P values from Shapiro-Wilk test, where the null hypothesis is a Gaussian distribution.

https://doi.org/10.1371/journal.pone.0246761.g001

To show asymptotic normality of distances, we did not specify whether the data distribution was discrete or continuous. This is because asymptotic normality is a general phenomenon in high attribute dimension p for any data distribution satisfying the assumptions we have made. Therefore, the simulated distances we have shown (Fig 1) have an analogous representation for discrete data, as well as all other continuous data distributions. In addition to showing Gaussian convergence for Manhattan and Euclidean distances on standard uniform data, we show a similar result for standard normal data (S2 Fig in S1 File).

For distance based learning methods, all pairwise distances are used to determine relative importances for attributes. The collection of all distances above the diagonal in an m × m distance matrix does not satisfy the independence assumption used in the previous derivations. This is because of the redundancy that is inherent to the distance matrix calculation. However, this collection is still asymptotically normal with mean and variance approximately equal to those we have previously given (Eq 8). In the next section, we assume actual data distributions in order to define more specific general formulas for standard L_q and max-min normalized L_q metrics. We also derive asymptotic moments for a new discrete metric in GWAS data and a new metric for time series correlation-based data, such as, resting-state fMRI.

3.1 Distribution of |d_ij(a)|^q = |X_ia − X_ja|^q

Suppose that and define , where and . In order to find the distribution of , we will use the following theorem given in [19].

Theorem 3.1 Let f(x) be the value of the probability density of the continuous random variable X at x. If the function given by y = u(x) is differentiable and either increasing or decreasing for all values within the range of X for which f(x)≠0, then, for these values of x, the equation y = u(x) can be uniquely solved for x to give x = w(y), and for the corresponding values of y the probability density of Y = u(X) is given by

Elsewhere, g(y) = 0.

We have the following cases that result from solving for X_ja in the equation given by :

1. Suppose that . Based on the iid assumption for X_ia and X_ja, it follows from Thm. 3.1 that the joint density function g⁽¹⁾ of X_ia and is given by (10)
   The density function of is then defined as (11)
2. Suppose that . Based on the iid assumption for X_ia and X_ja, it follows from Thm. 3.1 that the joint density function g⁽²⁾ of X_ia and Z_a is given by (12)
   The density function of is then defined as (13)

Let denote the distribution function of the random variable . Furthermore, we define the events E⁽¹⁾ and E⁽²⁾ as (14) and (15)

Then it follows from fundamental rules of probability that (16)

It follows directly from the previous result (Eq 16) that the density function of the random variable is given by (17) where z_a > 0.

Using the previous result (Eq 17), we can compute the mean and variance of the random variable as (18) and (19)

It follows immediately from the mean (Eq 18) and variance (Eq 19) and the Classical Central Limit Theorem (CCLT) that (20)

Applying the convergence result we derived previously (Eq 8), the distribution of is given by (21) where we have an improved estimate of the mean for q = 2 (Eq 9).

3.1.1 Standard normal data.

If , then the marginal density functions with respect to X for X_ia, , and are defined as (22) (23) (24)

Substituting these marginal densities (Eqs 22–24) into the general density function for (Eq 17) and completing the square on x_ia in the exponents, we have (25)

The density function given previously (Eq 25) is a Generalized Gamma density with parameters , c = 2^q, and . This distribution has mean and variance given by (26) and (27)

By linearity of the expected value and variance operators under the iid assumption, the mean (Eq 26) and variance (Eq 27) of the random variable allow the p- dimensional mean and variance of the distribution to be computed directly as (28) and (29)

Therefore, the asymptotic distribution of for standard normal data is (30)

As a useful reference, we tabulate the moment estimates (Eq 30) for the L_q metric on standard normal and uniform data (Fig 2). The derivations for standard uniform data are given in the next subsection. The table is organized by data type (normal or uniform), type of statistic (mean or variance), and corresponding asymptotic formula.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Summary of distance distribution derivations for standard normal () and standard uniform () data.

Asymptotic estimates are given for both standard (Eq 1) and max-min normalized (Eq 58) q-metrics. These estimates are relevant for all and p ≫ 1 for which the normality assumption of distances holds.

https://doi.org/10.1371/journal.pone.0246761.g002

3.2 Manhattan (L₁)

With our general formulas for the asymptotic mean and variance (Eqs 30 and 40) for any value of , we can simply substitute a particular value of q in order to determine the asymptotic distribution of the corresponding distance L_q metric. We demonstrate this with the example of the Manhattan metric (L₁) for standard normal and standard uniform data (Eq 1, q = 1).

3.2.1 Standard normal data.

Substituting q = 1 into the asymptotic formula for the mean L_q distance (Eq 30), we have the following for expected L₁ distance between two independently sample instances in standard normal data (41)

We see in the formula for the expected Manhattan distance (Eq 41) that in the limit, which implies that this distance is unbounded as feature dimension p increases.

Substituting q = 1 into the formula for the asymptotic variance of (Eq 30) leads to the following (42)

Similar to the mean (Eq 41), the limiting variance of (Eq 42) grows on the order of feature dimension p, which implies that points become more dispersed as the dimension increases. The summary of moment estimates given in this section (Eqs 41 and 42) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 3).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Asymptotic estimates of means and variances for the standard L₁ and L₂ (q = 1 and q = 2 in Fig 2) distance distributions.

Estimates for both standard normal () and standard uniform () data are given.

https://doi.org/10.1371/journal.pone.0246761.g003

3.3 Euclidean (L₂)

Moment estimates for the Euclidean metric are obtained by substituting q = 2 into the asymptotic moment formulas for standard normal data (Eq 30) and standard uniform data (Eq 40). As in the case of the Manhattan metric in the previous sections, we initially proceed by deriving Euclidean distance moments in standard normal data.

4.1 Distribution of max-min normalized L_q metric

We observe empirically that Gaussian convergence applies to the max-min normalized L_q metric in the case of continuous data. We show this behavior for the special cases of standard uniform (S1 Fig in S1 File) and standard normal (S3 Fig in S1 File). In order to determine moments of asymptotic max-min normalized distance (Eq 57) distributions, we will first derive the asymptotic extreme value distributions of the attribute maximum and minimum. Although the exact distribution of the maximum or minimum requires an assumption about the data distribution, the Fisher-Tippett-Gnedenko Theorem is an important result that allows one to generally categorize the extreme value distribution for a collection of independent and identically distributed random variables into one of three distributional families. This theorem does not, however, tell us the exact distribution of the maximum that we require in order to determine asymptotic results for the max-min normalized distance (Eq 58). We mention this theorem simply to provide some background on convergence of extreme values. Before stating the theorem, we first need the following definition

Definition 4.1 A distribution is said to be degenerate if its density function f_X is the Dirac delta δ(x − c₀) centered at a constant , with corresponding distribution function F_X defined as

Theorem 4.1 (Fisher-Tippett-Gnedenko) Let and let . If there exists two non-random sequences b_m > 0 and c_m such that where G_X is a non-degenerate distribution function, then the limiting distribution is in the Gumbel, Fréchet, or Wiebull family.

The three distribution families given in Theorem 4.1 are actually special cases of the Generalized Extreme Value Distribution. In the context of extreme values, Theorem 4.1 is analogous to the Central Limit Theorem for the distribution of sample mean. Although we will not explicitly invoke this theorem, it does tell us something very important about the asymptotic behavior of sample extremes under certain necessary conditions. For illustration of this general phenomenon of sample extremes, we derive the distribution of the maximum for standard normal data to show that the limiting distribution is in the Gumbel family, which is a known result. In the case of standard uniform data, we will derive the distribution of the maximum and minimum directly. Regardless of data type, the distribution of the sample maximum can be derived as follows (59)

Using more precise notation, the distribution function of the sample maximum in standard normal data is (60) where m is the size of the sample from which the maximum is derived and F_X is the distribution function corresponding to the data sample. This means that the distribution of the sample maximum relies only on the distribution function of the data from which extremes are drawn F_X and the size of the sample m.

Differentiating the distribution function (Eq 60) gives us the following density function for the distribution of the maximum (61) where m is the size of the sample from which the maximum is derived, F_X is the distribution function corresponding to the data sample, and f_X is the density function corresponding to the data sample. Similar to the distribution function for the sample maximum (Eq 60), the density function (Eq 61) relies only on the distribution and density function of the data from which extremes are derived.

The distribution of the sample minimum, , can be derived as follows (62) where m is the size of the sample from which the maximum is derived and F_X is the distribution function corresponding to the data sample. Therefore, the distribution of sample minimum also relies only on the distribution function of the data from which extremes are derived.

With more precise notation, we have the following expression for the distribution function of the minimum (63) where m is the size of the sample from which the minimum is derived and F_X is the distribution function corresponding to the data sample.

Differentiating the distribution function (Eq 63) gives us the following density function for the distribution of sample minimum (64) where m is the size of the sample from which the minimum is derived, F_X is the distribution function corresponding to the data sample, and f_X is the density function corresponding to the data sample. As in the case of the density function for sample maximum (Eq 61), the density function for sample minimum relies only on the distribution F_X and density f_X functions of the data from which extremes are derived and the sample size m.

Given the densities of the distribution of sample maximum and minimum, we can easily compute the raw moments and variance. The first moment about the origin of the distribution of sample maximum is given by the following (65) where m is the sample size, F_X is the distribution function, and f_X is the density function of the data from which the maximum is derived.

The second raw moment of the distribution of sample maximum is derived similarly as follows (66) where m is the sample size, F_X is the distribution function, and f_X is the density function of the data from which the maximum is derived.

Using the first (Eq 65) and second (Eq 66) raw moments of the distribution of sample maximum, the variance is given by (67) where m is the sample size of the data from which the maximum is derived and and are the first and second raw moments, respectively, of the distribution of sample maximum.

Moving on to the distribution of sample minimum, the first raw moment is given by the following (68) where m is the sample size, F_X is the distribution function, and f_X is the density function of the data from which the minimum is derived.

Similarly, the second raw moment of the distribution of sample minimum is given by the following (69) where m is the sample size, F_X is the distribution function, and f_X is the density function of the data from which the minimum is derived.

Using the first (Eq 68) and second (Eq 69) raw moments of the distribution of sample minimum, the variance is given by (70) where m is the sample size of the data from which the maximum is derived and and are the first and second raw moments, respectively, of the distribution of sample maximum.

Using the expected attribute maximum (Eq 65) and minimum (Eq 68) for sample size m, the following expected attribute range results from linearity of the expectation operator (71) where is the expected sample maximum (Eq 65) and is the expected sample minimum.

For a data distribution whose density is an even function, the expected attribute range (Eq 71) can be simplified to the following expression (72) where m is the size of the sample from which the maximum is derived. Hence, the expected attribute range is simply twice the expected attribute maximum (Eq 65). This result naturally applies to standard normal data, which is symmetric about its mean at 0 and without any skewness.

For large samples (m ≫ 1) from an exponential type distribution that has infinite support and all moments, the covariance between the sample maximum and minimum is approximately zero [22]. In this case, the variance of the attribute range of a sample of size m is given by the following (73)

Under the assumption of zero skewness, infinite support and even density function, sufficiently large sample size m, and distribution of an exponential type for all moments, the variance of attribute range (Eq 73) simplifies to the following (74)

Let and (Eq 21) denote the mean and variance of the standard L_q distance metric (Eq 1). Then the expected value of the max-min normalized distance (Eq 58) distribution is given by the following (75) where m is the size of the sample from which extremes are derived, is the expected value of the sample maximum (Eq 65), and is the expected value of the sample minimum.

The variance of the max-min normalized distance (Eq 58) distribution is given by the following (76) where m is the size of the sample from which extremes are derived, is the expected value of the sample maximum (Eq 65), and is the expected value of the sample minimum.

With the mean (Eq 75) and variance (Eq 76) of the max-min normalized distance (Eq 58), we have the following generalized estimate for the asymptotic distribution of the max-min normalized distance distribution (77) where m is the size of the sample from which extremes are derived, is the expected value of the sample maximum (Eq 65), and is the expected value of the sample minimum.

For data with zero skewness, infinite support, and even density function, the expected sample maximum is the additive inverse of the expected sample minimum. This allows us to express the expected max-min normalized pairwise distance (Eq 75) exclusively in terms of the expected sample maximum. This result is given by the following (78) where m is the size of the sample from which the maximum is derived and is the expected value of the sample maximum (Eq 65).

A similar substitution gives us the following expression for the variance of the max-min normalized distance distribution (79) where m is the size of the sample from which extremes are derived, is the expected value of the sample maximum (Eq 65), and is the variance of the sample maximum (Eq 67).

Therefore, the asymptotic distribution of the max-min normalized distance distribution (Eq 77) becomes (80) where m is the size of the sample from which extremes are derived, is the expected value of the sample maximum (Eq 65), and is the variance of the sample maximum (Eq 67).

We have now derived asymptotic estimates of the moments of the max-min normalized L_q distance metric (Eq 58) for any continuous data distribution. In the next two sections, we examine the max-min normalized L_q distance on standard normal and standard uniform data. As in previous sections in which we analyzed the standard L_q metric (Eq 1), we will use the more general results for the max-min L_q metric to derive asymptotic estimates for normalized Manhattan (q = 1) and Euclidean (q = 2).

4.1.1 Standard normal data.

The standard normal distribution has zero skewness, even density function, infinite support, and all moments. This implies that the corresponding mean and variance of the distribution of sample range can be expressed exclusively in terms of the sample maximum. Given the nature of the density function of the sample maximum for sample size m, the integration required to determine the moments (Eqs 65 and 66) is not possible. These moments can either be approximated numerically or we can use extreme value theory to determine the form of the asymptotic distribution of the sample maximum. Using the latter method, we will show that the asymptotic distribution of the sample maximum for standard normal data is in the Gumbel family. Let and , where Φ is the standard normal cumulative distribution function. Using Taylor’s Theorem, we have the following expansion (81) where m is the size of the sample from which the maximum is derived.

In order to simplify the right-hand side of this expansion (Eq 81), we will use the Mills Ratio Bounds [23] given by the following (82) where Φ and ϕ once again represent the cumulative distribution function and density function, respectively, of the standard normal distribution.

The inequalities given above (Eq 82) show that

This further implies that since

This gives us the following approximation of the right-hand side of the expansion (Eq 81) given previously (83) where m is the size of the sample from which the maximum is derived.

Using the approximation of expansion given previously (Eq 83), we now derive the limit distribution for the sample maximum in standard normal data as (84) which is the cumulative distribution function of the standard Gumbel distribution. The mean of this distribution is given by the following (85) where m is the size of the sample from which the maximum is derived and γ is the Euler-Mascheroni constant. This constant has many equivalent definitions, one of which is given by

Perhaps a more convenient definition of the Euler-Mascheroni constant is simply which is just the additive inverse of the first derivative of the gamma function evaluated at 1.

The median of the distribution of the maximum for standard normal data is given by (86) where m is the size of the sample from which the maximum is derived.

Finally, the variance of the asymptotic distribution of the sample maximum is given by (87) where m is the size of the sample from which the maximum is derived.

For typical sample sizes m in high-dimensional spaces, the variance estimate (Eq 87) exceeds the variance of the sample maximum significantly. Using the fact that [24] and we can get a more accurate approximation of the variance with the following (88)

Therefore, the mean of the range of m iid standard normal random variables is given by (89) where γ is the Euler-Mascheroni constant.

It is well known that the sample extremes from the standard normal distribution are approximately uncorrelated for large sample size m [22]. This implies that we can approximate the variance of the range of m iid standard normal random variables with the following result (90)

For the purpose of approximating the mean and variance of the max-min normalized distance distribution, we observe empirically that the formula for the median of the distribution of the attribute maximum (Eq 86) yields more accurate results. More precisely, the approximation of the expected maximum (Eq 85) overestimates the sample maximum slightly. The formula for the median of the sample maximum (Eq 86) provides a more accurate estimate of this sample extreme. Therefore, the following estimate for the mean of the attribute range will be used instead (91) where m is the size of the sample from which extremes are derived.

We have already determined the mean and variance (Eq 30) for the L_q metric (Eq 1) on standard normal data. Using the expected value of the sample maximum (Eq 91), the variance of the sample maximum (Eq 90), and the general formulas for the mean and variance of the max-min normalized distance distribution (Eq 80), this leads us to the following asymptotic estimate for the distribution of the max-min normalized distances for standard normal data (92) where m is the size of the sample from which the maximum is derived, is the median of the sample maximum (Eq 86), is the expected L_q pairwise distance (Eq 28), and is the variance of the L_q pairwise distance (Eq 29). The summary of moments of the max-min normalized L_q distance metric in standard normal data (Eq 92) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Asymptotic estimates of means and variances for the max-min normalized L₁ and L₂ distance distributions commonly used in Relief-based algorithms.

Estimates for both standard normal () and standard uniform () data are given. The cumulative distribution function of the standard normal distribution is represented by Φ. Furthermore, (Eq 86) is the asymptotic median of the sample maximum from m standard normal random samples.

https://doi.org/10.1371/journal.pone.0246761.g004

4.2 Range-Normalized Manhattan (q = 1)

Using the general asymptotic results for mean and variance of max-min normalized distances in standard normal and standard uniform data (Eqs 92 and 100) for any value of , we can substitute a particular value of q in order to determine a more specified distribution for the normalized distance (D^(q*), Eq 58). The following results are for the max-min normalized Manhattan (q = 1), D^(1*), metric for both standard normal and standard uniform data.

4.3 Range-Normalized Euclidean (q = 2)

Analogous to the previous section, we use the asymptotic moment estimates for the max-min normalized metric (D^(q*), Eq 58) for standard normal (Eq 92) and standard uniform (Eq 100) data but specific to a range-normalized Euclidean metric (q = 2).

5.1 GM distance distribution

The simplest distance metric in nearest-neighbor feature selection in GWAS data is the genotype-mismatch (GM) distance metric (Eq 113). The GM attribute diff (Eq 110) indicates only whether two genotypes are the same or not. There are many ways two genotypes could differ, but this metric does not record this information. We will now derive the moments for the GM distance (Eq 113), which are sufficient for defining its corresponding asymptotic distribution.

The expected value of the GM attribute diff metric (Eq 110) is given by the following (116) where and f_a is the probability of a minor allele occurring at locus a.

Then the expected pairwise GM distance between instances is given by (117) where and f_a is the probability of a minor allele occurring at locus a. We see that the expected GM pairwise distance (Eq 117) relies only on the minor allele probabilities f_a for all . In real data, we can easily determine these probabilities by dividing the total number of minor alleles at locus a by the twice the number of instances m. To be more explicit, this is just where m is the number of instances (or sample size). This is because each instance has two alleles, the minor and major alleles, at each locus. Therefore, the total number of alleles at locus a is 2m.

The second moment about the origin for the GM distance is computed as follows (118) where and f_a is the probability of a minor allele occurring at locus a.

Using the first (Eq 117) and second (Eq 118) raw moments of the GM distance, the variance is given by (119) where and f_a is the probability of a minor allele occurring at locus a. Hence, the variance of the asymptotic GM distance distribution also just depends on the minor allele probabilities f_a for all . This implies that the limiting GM distance distribution is fully determined by the minor allele probabilities, which are known in real data.

With the mean and variance estimates (Eqs 117 and 119), the asymptotic GM distance distribution is given by the following (120) where and f_a is the probability of a minor allele occurring at locus a. This GM distribution holds for random independent GWAS data with minor allele probabilities f_a and binomial samples for all . Next we consider the distance distribution for an AM metric, which incorporates differences at the allele level and contains more information than genotype differences.

5.2 AM distance distribution

As we have mentioned previously, the AM attribute diff metric (Eq 111) is slightly more dynamic than the GM metric because the AM metric accounts for differences between the alleles of two genotypes. In this section, we derive moments of the AM distance metric (Eq 114) that adequately define its corresponding asymptotic distribution.

The expected value of the AM attribute diff metric (Eq 111) is given by the following (121) where , , and f_a is the probability of a minor allele occurring at locus a.

Using the expected AM attribute diff (Eq 121), the expected pairwise AM distance (Eq 114) between instances is given by (122) where and f_a is the probability of a minor allele occurring at locus a. Similar to GM distances, the expected AM distance (Eq 122) depends only on the minor allele probabilities f_a for all . This is to be expected because, although the AM metric is more informative, it still only accounts for simple differences between nucleotides of two instances at some locus a.

The second moment about the origin for the AM distance is computed as follows (123) where , , and f_a is the probability of a minor allele occurring at locus a.

Using the first (Eq 122) and second (Eq 123) raw moments of the asymptotic AM distance distribution, the variance is given by (124) where , , and f_a is the probability of a minor allele occurring at locus a. Similar to the mean (Eq 122), the variance just depends on minor allele probabilities f_a for all .

With the mean (Eq 122) and variance (Eq 124) estimates of AM distances, the asymptotic AM distance distribution is given by the following (125) where , , and f_a is the probability of a minor allele occurring at locus a.

This concludes our analysis of the AM metric in GWAS data when the independence assumption holds for minor allele probabilities f_a and binomial samples for all . In the next section, we derive more complex asymptotic results for the TiTv distance metric (Eq 115).

5.3 TiTv distance distribution

The TiTv metric allows for one to account for both genotype mismatch, allele mismatch, transition, and transversion. However, this added dimension of information requires knowledge of the nucleotide makeup at a particular locus. A sufficient condition to compute the TiTv metric between instances is that we know whether the nucleotides associated with a particular locus a are both purines (PuPu), purine and pyrimidine (PuPy), or both pyrimidines (PyPy). We illustrate all possibilities for transitions and transversions in a diagram (Fig 5). Purines (A and G) and pyrimidines (C and T) are shown at the top and bottom, respectively. Transitions occur in the cases of PuPu and PyPy, while transversion occurs only with PuPy encoding.

This additional encoding is always given in a particular GWAS data set, which leads us to consider the probabilities of PuPu, PuPy, and PyPy. These will be necessary to determine asymptotics for the TiTv distance metric. Let γ₀, γ₁, and γ₂ denote the probabilities of PuPu, PuPy, and PyPy, respectively, for the p loci of data matrix X. In real data, there are approximately twice as many transitions as there are transversions. That is, the probability of a transition P(Ti) is approximately twice the probability of transversion P(Tv). It is likely that any particular data set will not satisfy this criterion exactly. In this general case, we have P(Ti) being equal to some multiple η times P(Tv). In order to enforce this general constraint in simulated data, we define the following set of equalities (126) (127)

The sum-to-one constraint (Eq 126) is natural in this context because there are only three possible genotype encodings at a particular locus, which are PuPu, PuPy, and PyPy. Solving the Ti/Tv ratio constraint (Eq 127) for η gives which is easily computed in a real data set by dividing the fraction of Ti out of the total p loci by the fraction of Tv out of the total p loci. We will use the simplified notation η = Ti/Tv to represent this factor for the remainder of this work.

Using this PuPu, PuPy, and PyPy encoding, the probability of a transversion occurring at any fixed locus a is given by the following (128)

Using the sum-to-one constraint (Eqs 126) and the probability of transversion (Eq 127), the probability of a transition occuring at locus a is computed as follows (129)

Also using the sum-to-one constraint (Eq 126) and the Ti/Tv ratio constraint (Eq 127), it is clear that we have and . Without loss of generality, we then sample (130) where ε is some small positive real number.

Then it immediately follows that we have (131)

However, we can derive the mean and variance of the distance distribution induced by the TiTv metric without specifying any relationship between γ₀, γ₁, and γ₂. We proceed by computing for each . Let y represent a random sample of size p from {0, 1, 2}, where (132)

We derive as follows (133) where f_a is the probability of a minor allele occurring at locus a.

We derive as follows (134) where f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a.

We derive as follows (135) where f_a is the probability of a minor allele occurring at locus a and γ₁ is the probability of PuPy occurring at any locus a.

We derive as follows (136) where f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a.

We derive as follows (137) where f_a is the probability of a minor allele occurring at locus a and γ₁ is the probability of PuPy occurring at any locus a.

Using the TiTv diff probabilities (Eqs 133–137), we compute the expected TiTv distance between instances as follows (138) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, γ₁ is the probability of PuPy occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a. In contrast to the expected GM and AM distances (Eqs 117 and 122), the expected TiTv distance (Eq 138) depends on minor allele probabilities f_a for all and the genotype encoding probabilities γ₀, γ₁, and γ₂.

The second moment about the origin for the TiTv distance is computed as follows (139) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, γ₁ is the probability of PuPy occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a.

Using the first (Eq 138) and second (Eq 139) raw moments of the TiTv distance, the variance is given by (140) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, γ₁ is the probability of PuPy occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a.

With the mean (Eq 138) and variance (Eq 140) estimates, the asymptotic TiTv distance distribution is given by the following (141) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu occurring at any locus a, γ₁ is the probability of PuPy occurring at any locus a, and γ₂ is the probability of PyPy occurring at any locus a.

Given upper and lower bounds l and u, respectively, of the success probability sampling interval, the average success probability (or average MAF) is computed as follows (142)

The maximum TiTv distance occurs at for any fixed Ti/Tv ratio η (Eq 127), which is the inflection point about which the minor allele changes at locus a (Fig 6). If few minor alleles are present (), the predicted TiTv distance approaches 0. The same is true after the minor allele switches (). To explore how TiTv distance changes with increased minor allele frequency, we fixed the Ti/Tv ratio η and generated simulated TiTv distances for (Fig 7A). For fixed η, TiTv distance increases significantly with increased . We similarly fixed the average minor allele frequency and generated simulated TiTv distances for η = Ti/Tv = 0.5, 1, 1.5, and 2 (Fig 7C). The TiTv distance decreases slightly with increased η = Ti/Tv. As η → 0⁺, the data is approaching all Tv and no Ti, which means the TiTv distance is larger by definition. On the other hand, the TiTv distance decreases as η → 2⁻ because the data is approaching approximately twice as many Ti as there are Tv, which is typical for GWAS data in humans.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. Predicted average TiTv distance as a function of average minor allele frequency (see Eq 142).

Success probabilities f_a are drawn from a sliding window interval from 0.01 to 0.9 in increments of about 0.009 and m = p = 100. For η = 0.1, where η is the Ti/Tv ratio given by Eq 126, Tv is ten times more likely than Ti and results in larger distance. Increasing to η = 1, Tv and Ti are equally likely and the distance is lower. In line with real data for η = 2, Tv is half as likely as Ti so the distances are relatively small.

https://doi.org/10.1371/journal.pone.0246761.g006

We also compared theoretical and sample moments as a function of η = Ti/Tv and for the TiTv distance metric (Fig 7B and 7D). We fixed and computed the theoretical and simulated moments as a function of η (Fig 7B). Theoretical average TiTv distance (Eq 138) and simulated TiTv average distance are approximately equal as η increases. Theoretical standard deviation (Eq 140) and simulated TiTv standard deviation differ slightly. We also fixed η and computed theoretical and sample moments as a function of (Fig 7D). In this case, there is approximate agreement with simulated and theoretical moments as increases.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. Density curves and moments of TiTv distance as a function of average MAF , given by Eq 142, and Ti/Tv ratio η, given by Eq 127.

We fix m = p = 100 for all simulated TiTv distances. (A) For fixed , TiTv distance density is plotted as a function of increasing η. TiTv distance decreases as η increases. For η = Ti/Tv = 0.5, there are twice as many transversions as there are transitions. On the other hand, η = Ti/Tv = 2 indicates that there are half as many transversions as transitions. Since transversions encode a larger magnitude distance than transitions, this behavior is expected. (B) Simulated and predicted mean ± SD are shown as a function of increasing Ti/Tv ratio η. Distance decreases as Ti/Tv increases. Theoretical and simulated moments are approximately the same. (C) For fixed η = 2, TiTv distance density is plotted as a function of increasing . TiTv distance increases as approaches maximum of 0.5, which means that there is about the same frequency of minor alleles as major alleles. (D) Simulated and predicted mean ± SD as a function of increasing average MAF . Distance increases as the number of minor alleles increases. Theoretical and simulated moments are approximately the same.

https://doi.org/10.1371/journal.pone.0246761.g007

We summarize our moment estimates for GWAS distance metrics (Eqs 113–115) (Fig 8) organized by metric, statistic (mean or variance), and asymptotic formula. Next we consider the important case of distributions of GWAS distances projected onto a single attribute (Eqs 110–112).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 8. Asymptotic estimates of means and variances of genotype mismatch (GM) (Eq 113), allele mismatch (AM) (Eq 114), and transition-transversion (TiTv) (Eq 115) distance metrics in GWAS data (p ≫ 1).

GWAS data , where f_a for all are the probabilities of a minor allele occurring at locus a. For the TiTv distance metric, we have the additional encoding that uses γ₀ = P(PuPu), γ₁ = P(PuPy), and γ₂ = P(PyPy).

https://doi.org/10.1371/journal.pone.0246761.g008

5.4 Distribution of one-dimensional projection of GWAS distance onto a SNP

We previously derived the exact distribution of the one-dimensional projected distance onto an attribute in continuous data (Section 3.2.3), which is used as the predictor in NPDR to calculate relative attribute importance in the form of standardized beta coefficients. GWAS data and the metrics we have considered are discrete. Therefore, we derive the density function for each diff metric (Eqs 110–112), which also serves as the probability distribution for each metric, respectively.

The support of the GM metric (Eq 110) is simply {0, 1}, so we derive the probability, , of this diff taking on each of these two possible values. First, the probability that the GM diff is equal to zero is given by (143) where f_a is the probability of a minor allele occurring at locus a.

Similarly, the probability that the GM diff is equal to 1 is derived as follows (144) where f_a is the probability of a minor allele occurring at locus a.

This leads us to the probability distribution of the GM diff metric, which is the distribution of the one-dimensional GM distance projected onto a single SNP. This distribution is given by (145) where f_a is the probability of a minor allele occurring at locus a.

The mean and variance of this GM diff distribution can easily be derived using this newly determined density function (Eq 145). The average GM diff is given by the following (146) where and f_a is the probability of a minor allele occurring at locus a.

The variance of the GM diff metric is given by (147) where and f_a is the probability of a minor allele occurring at locus a.

The support of the AM metric (Eq 111) is {0, 1/2, 1}. Beginning with the probability of the AM diff being equal to 0, we have the following probability (148) where f_a is the probability of a minor allele occurring at locus a.

The probability of the AM diff metric being equal to 1/2 is computed similarly as follows (149) where f_a the probability of a minor allele occurring at locus a.

Finally, the probability of the AM diff metric being equal to 1 is given by the following (150) where f_a is the probability of a minor allele occurring at locus a.

As in the case of the GM diff metric, we now have the probability distribution of the AM diff metric. This also serves as the distribution of the one-dimensional AM distance projected onto a single SNP, and is given by the following (151) where f_a is the probability of a minor allele occurring at locus a.

The mean and variance of this AM diff distribution is derived using the corresponding density function (Eq 151). The average AM diff is given by (152) where and f_a is the probability of a minor allele occurring at locus a.

The variance of the AM diff metric is given by (153) where , , f_a is the probability of a minor allele occurring at locus a.

For the TiTv diff metric (Eq 112), the support is {0, 1/4, 1/2, 3/4, 1}. We have already derived the probability that the TiTv diff assumes each of the values of its support (Eqs 133–137). Therefore, we have the following distribution of the TiTv diff metric (154) where f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu at locus a, γ₁ is the probability of PuPy at locus a, γ₂ is the probability of PyPy at locus a, and η is the Ti/Tv ratio (Eq 127).

The mean and variance of this TiTv diff distribution is derived using the corresponding density function (Eq 154). The average TiTv diff is given by (155) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu at locus a, γ₁ is the probability of PuPy at locus a, and γ₂ is the probability of PyPy at locus a.

The variance of the TiTv diff metric is given by (156) where , , f_a is the probability of a minor allele occurring at locus a, γ₀ is the probability of PuPu at locus a, γ₁ is the probability of PuPy at locus a, and γ₂ is the probability of PyPy at locus a.

These novel distribution results for the projection of pairwise GWAS distances onto a single genetic variant, as well as results for the full space of p variants, can inform NPDR and other nearest-neighbor distance-based feature selection algorithms. We show density curves for GM (S23 Fig in S1 File), AM (S24 Fig in S1 File), and TiTv (S25 Fig in S1 File) for each possible support value. Next we introduce our new diff metric and distribution results for time-series derived correlation-based data, with a particular application to resting-state fMRI.

6.1 Max-min normalized time series correlation-based distance distribution

Previously (Section 4) we determined the asymptotic distribution of the sample maximum of size m from a standard normal distribution. We can naturally extend these results to our transformed rs-fMRI data because X (Fig 9) is approximately standard normal. Furthermore, we have previously mentioned that the max-min normalized L_q metric yields approximately normal distances with the iid assumption. We show a similar result for max-min normalized rs-fMRI distances (S8 Fig in S1 File). We proceed with the definition of the max-min normalized rs-fMRI pairwise distance.

Consider the max-min normalized rs-fMRI distance given by the following equation (166)

Assuming that the data X has been r-to-z transformed and standardized, we can easily compute the expected attribute range and variance of the attribute range. The expected maximum of a given attribute in data matrix X is estimated by the following (167)

The variance can be esimated with the following (168)

Let and denote the mean and variance of the rs-fMRI distance distribution given by Eqs 159 and 164. Using the formulas for the mean and variance of the max-min normalized distance distribution given in Eq 92, we have the following asymptotic distribution for the max-min normalized rs-fMRI distances (169)

6.2 One-dimensional projection of rs-fMRI distance onto a single ROI

Just as in previous sections (Sections. 3.2.3 and 5.4), we now derive the distribution of our rs-fMRI diff metric (Eq 157). Unlike what we have seen in previous sections, we do not derive the exact distribution for this diff metric. We have determined empirically that the rs-fMRI diff is approximately normal. Although the rs-fMRI diff is a sum of p − 1 magnitude differences, the Classical Central Limit Theorem does not apply because of the dependencies that exist between the terms of the sum. Examination of histograms and quantile-quantile plots of simulated values of the rs-fMRI diff easily indicate that the normality assumption is safe. Therefore, we derive the mean and variance of the approximately normal distribution of the rs-fMRI diff. As we have seen previously, this normality assumption is reasonable even for small values of p.

The mean of the rs-fMRI diff is derived by fixing a single ROI a and considering all pairwise associations with other ROIs . This is done as follows (170) where a is a single fixed ROI.

Considering the variance of the rs-fMRI diff metric, we have two estimates. The first estimate uses the variance operator in a linear fashion, while the second will simply be a direct implication of the corrected formula of the variance of rs-fMRI pairwise distances (Eq 164). Our first estimate is derived as follows (171) where a is a single fixed ROI.

Using the corrected rs-fMRI distance variance formula (Eq 164), our second estimate of the rs-fMRI diff variance is given directly by the following (172) where a is a single fixed ROI.

Empirically, the first estimate (Eq 171) of the variance of our rs-fMRI diff is closer to the sample variance than the second estimate (Eq 172). This is due to fact that we are considering only a fixed ROI , so the cross-covariance between the magnitude differences for different pairs of ROIs (a and k ≠ a) is negligible here. When considering all ROIs , these cross-covariances are no longer negligible. Using the first variance estimate (Eq 171) and the estimate of the mean (Eq 170), we have the following asymptotic distribution of the rs-fMRI diff (173) where a is a single fixed ROI. We compare moment estimates for the rs-fMRI diff (Eqs 170 and 171) with sample moments from simulated data with m = 100 samples and p = 1000, 2000, …, 5000 attributes (S21 Fig in S1 File). Our estimates follow the sample moments from simulated data very closely.

6.3 Normalized Manhattan (q = 1) for rs-fMRI

Substituting the non-normalized mean (Eq 159) into the equation for the mean of the max-min normalized rs-fMRI metric (Eq 169), we have the following (174) where (Eq 167) is the expected maximum of a single ROI in a data set with m instances and p ROIs.

Similarly, the variance of is given by (175) where (Eq 167) is the expected maximum of a single ROI in a data set with m instances and p ROIs.

We summarize the moment estimates for the rs-fMRI metrics for correlation-based data derived from time series (Fig 10). We organize this summary by standard and attribute range-normalized rs-fMRI distance metric, statistic (mean or variance), and asymptotic formula.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 10. Aymptotic means and variances for the new standard (Eq 158) and max-min normalized (Eq 166) rs-fMRI distance metrics.

https://doi.org/10.1371/journal.pone.0246761.g010

8.1 Continuous data

Without loss of generality, suppose we have X^(m×p) where for all i = 1, 2, …, m and a = 1, 2, …, p, and let m = p = 100. We consider only the L₂ (Euclidean) metric (Eq 1, q = 2). We explore the effects of correlation on these distances by generating simulated data sets with increasing strength of pairwise attribute correlation and then plotting the density curve of the induced distances (Fig 12A). Deviation from normality in the distance distribution is directly related to the average absolute pairwise correlation that exists in the simulated data. This measure is given by (176) where r_ak is the correlation between attributes across all instances m. Distances generated on data without correlation closely approximate a Gaussian. The mean (Eq 53) and variance (Eq 52) of the uncorrelated distance distribution are given by substituting p = 100 for the mean. As increases, positive skewness and increased variability in distances emerges. The predicted and sample means, however, are approximately the same between correlated and uncorrelated distances due to linearity of the expectation operator. Because of the dependencies between attributes, the predicted variance of 1 for L₂ on standard normal data obviously no longer holds.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 12. Distance densities from uncorrelated vs correlated bioinformatics data.

(A) Euclidean distance densities for random normal data with and without correlation. Correlated data was created by multiplying random normal data by upper-triangular Cholesky factor from randomly generated correlation matrix. We created correlated data for average absolute pairwise correlation (Eq 176) . (B) TiTv distance densities for random binomial data with and without correlation. Correlated data was created by first generating correlated standard normal data using the Cholesky method from (A). Then we applied the standard normal CDF to create correlated uniformly distributed data, which was then transformed by the inverse binomial CDF with n = 2 trials and success probabilites . (C) Time series correlation-based distance densities for random rs-fMRI data (Fig 9) with and without additional pairwise feature correlation. Correlation was added to the transformed rs-fMRI data matrix (Fig 9) using the Cholesky algorithm from (A).

https://doi.org/10.1371/journal.pone.0246761.g012

In order to introduce a controlled level of correlation between attributes, we created correlation matrices based on a random graph with specified connection probability, where attributes correspond to the vertices in each graph. We assigned high correlations to connected attributes from the random graph and low correlations to all non-connections. Using the upper-triangular Cholesky factor U for uncorrelated data matrix X, we computed the following product to create correlated data matrix X^corr (177)

The new data matrix X^corr has approximately the same correlation structure as the randomly generated correlation matrix created from a random graph.

8.2 GWAS data

Analogous to the previous section, we explore the effects of pairwise attribute correlation in the context of GWAS data. Without loss of generality, we let m = p = 100 and consider only the TiTv metric (Eq 115). To create correlated GWAS data, we first generated standard normal data with random correlation structure, just as in the previous section. We then applied the standard normal cumulative distribution function (CDF) to this correlated data in order transform the correlated standard normal variates into uniform data with preserved correlation structure. We then subsequently applied the inverse binomial CDF to the correlated uniform data with random success probabilities . Each attribute corresponds to an individual SNP in the data matrix. The resulting GWAS data set is binomial with n = 2 trials and has roughly the same correlation matrix as the original correlated standard normal data with which we started. Average absolute pairwise correlation induces positive skewness in GWAS data at lower levels than in correlated standard normal data (Fig 12B). This could have important implications in nearest neighborhoods in NPDR and similar methods.

8.3 Time-series derived correlation-based datasets

For our correlation data-based metric (Eq 158), we consider additional effects of correlation between features. Without loss of generality, we let m = 100 and p = 30. We show an illustration of the effects of correlated features in this context (Fig 12C). Based on the density estimates, it appears that correlation between features introduces positive skewness at low values of . We introduced correlation to the transformed data matrix (Fig 9) with the cholesky method used previously.