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

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 $$ i\in \mathcal{I}$$. 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 $$ i,j\in \mathcal{I}$$ (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 $$ X_{ia},X_{ja}\stackrel{iid}{\sim }{\mathcal{F}}_X({\mu }_X,{\sigma }_X^2)$$ for two fixed and distinct instances $$ i,j\in \mathcal{I}$$ and a fixed attribute $$ a\in \mathcal{A}$$. $$ {\mathcal{F}}_X$$ represents any data distribution with mean μ_X and variance $$ {\sigma }_X^2$$.

It is clear that |X_ia − X_ja|^q = |d_ij(a)|^q is another random variable, so we let $$ Z_a^q\sim {\mathcal{F}}_{Z_a^q}({\mu }_{z_a^q},{\sigma }_{z_a^q}^2)$$ be the random variable such that

Furthermore, the collection $$ \left\{Z_a^q\right|a\in \mathcal{A}\}$$ is a random sample of size p of mutually independent random variables. Hence, the sum of $$ Z_a^q$$ over all $$ a\in \mathcal{A}$$ is asymptotically normal by the Classical Central Limit Theorem (CCLT). More explicitly, this implies that

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

Therefore, the distance between two fixed, distinct instances i and j (Eq 1) is asymptotically normal. In particular, when q = 2, the distribution of $$ D_{ij}^{\left(2\right)}$$ asymptotically approaches $$ \mathcal{N}(\sqrt{{\mu }_{z_a^2}p},\frac{{\sigma }_{z_a^2}^2}{4{\mu }_{z_a^2}})$$. 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

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.

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.

To show asymptotic normality of distances, we did not specify whether the data distribution $$ {\mathcal{F}}_X$$ was discrete or continuous. This is because asymptotic normality is a general phenomenon in high attribute dimension p for any data distribution $$ {\mathcal{F}}_X$$ 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 $$ X_{ia},X_{ja}\stackrel{iid}{\sim }{\mathcal{F}}_X({\mu }_x,{\sigma }_x^2)$$ and define $$ Z_a^q=|{\text{d}}_{ij}{\left(a\right)|}^q={|X_{ia}-X_{ja}|}^q$$, where $$ a\in \mathcal{A}$$ and $$ \left|\mathcal{A}\right|=p$$. In order to find the distribution of $$ Z_a^q$$, 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 $$ Z_a^q={|X_{ia}-X_{ja}|}^q$$:

Suppose that $$ X_{ja}=X_{ia}-{\left(Z_a^q\right)}^{1/q}$$. 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^q$$ is given by



The density function $$ f_{Z_a^q}^{\left(1\right)}$$ of $$ Z_a^q$$ is then defined as



Suppose that $$ X_{ja}=X_{ia}+{\left(Z_a^q\right)}^{1/q}$$. 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



The density function $$ f_{Z_a^q}^{\left(2\right)}$$ of $$ Z_a^q$$ is then defined as

Let $$ F_{Z_a^q}$$ denote the distribution function of the random variable $$ Z_a^q$$. Furthermore, we define the events E⁽¹⁾ and E⁽²⁾ as

Then it follows from fundamental rules of probability that

It follows directly from the previous result (Eq 16) that the density function of the random variable $$ Z_a^q$$ is given by

Using the previous result (Eq 17), we can compute the mean and variance of the random variable $$ Z_a^q$$ as

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

Applying the convergence result we derived previously (Eq 8), the distribution of $$ D_{ij}^{\left(q\right)}$$ is given by

3.1.1 Standard normal data

If $$ X_{ia},X_{ja}\stackrel{iid}{\sim }\mathcal{N}(0,1)$$, then the marginal density functions with respect to X for X_ia, $$ X_{ia}-{\left(Z_a^q\right)}^{1/q}$$, and $$ X_{ia}+{\left(Z_a^q\right)}^{1/q}$$ are defined as

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

The density function given previously (Eq 25) is a Generalized Gamma density with parameters $$ b=\frac{2}{q}$$, c = 2^q, and $$ d=\frac{1}{q}$$. This distribution has mean and variance given by

and

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 $$ Z_a^q$$ allow the p- dimensional mean and variance of the $$ {\left(D_{ij}^{\left(q\right)}\right)}^q$$ distribution to be computed directly as

and

Therefore, the asymptotic distribution of $$ D_{ij}^{\left(q\right)}$$ for standard normal data is

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.

Fig 2

Summary of distance distribution derivations for standard normal ($$ \mathcal{N}(0,1)$$) and standard uniform ($$ \mathcal{U}(0,1)$$) data.

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

3.1.2 Standard uniform data

If $$ X_{ia},X_{ja}\stackrel{iid}{\sim }\mathcal{U}(0,1)$$, then the marginal density functions with respect to X for X_ia, $$ X_{ia}-{\left(Z_a^q\right)}^{1/q}$$, and $$ X_{ia}+{\left(Z_a^q\right)}^{1/q}$$ are defined as

Substituting these marginal densities (Eqs 31–33) into the more general density function for $$ Z_a^q$$ (Eq 17), we have

The previous density (Eq 34) is a Kumaraswamy density with parameters $$ b=\frac{1}{q}$$ and c = 2 with moment generating function (MGF) given by

Using this MGF (Eq 35), the mean and variance of $$ Z_a^q$$ are computed as

and

By linearity of the expected value and variance operators under the iid assumption, the mean (Eq 36) and variance (Eq 37) of the random variable $$ Z_a^q$$ allow the p- dimensional mean and variance of the $$ {\left(D_{ij}^{\left(q\right)}\right)}^q$$ distribution to be computed directly as

and

Therefore, the asymptotic distribution of $$ D_{ij}^{\left(q\right)}$$ for standard uniform data is

As previously noted, we tabulate the moment estimates (Eq 40) for the L_q metric on standard uniform data along with standard normal data (Fig 2). The summary is organized by data type (normal or uniform), type of statistic (mean or variance), and corresponding asymptotic formula. In the next subsections, we show the asymptotic moments of the distance distribution for standard normal and standard uniform data for the special case of Manhattan (q = 1) and Euclidean (q = 2) metrics. These are the most commonly applied metrics in the context of nearest-neighbor feature selection, so they are of particular interest.

3.2 Manhattan (L₁)

With our general formulas for the asymptotic mean and variance (Eqs 30 and 40) for any value of $$ q\in \mathbb{N}$$, 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 $$ i,j\in \mathcal{I}$$ in standard normal data

We see in the formula for the expected Manhattan distance (Eq 41) that $$ D_{ij}^{\left(1\right)}\sim p$$ 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 $$ D_{ij}^{\left(1\right)}$$ (Eq 30) leads to the following

Similar to the mean (Eq 41), the limiting variance of $$ D_{ij}^{\left(1\right)}$$ (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).

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 ($$ \mathcal{N}(0,1)$$) and standard uniform ($$ \mathcal{U}(0,1)$$) data are given.

3.2.2 Standard uniform data

Substituting q = 1 into the asymptotic formula of the mean (Eq 40), we have the following for the expected L₁ distance between two independently sampled instances $$ i,j\in \mathcal{I}$$ in standard uniform data

Once again, we see that the mean of $$ D_{ij}^{\left(1\right)}$$ (Eq 43) grows on the order of p just as in the case of standard normal data.

Substituting q = 1 into the formula of the asymptotic variance of $$ D_{ij}^{\left(1\right)}$$ (Eq 40) leads to the following

As in the case of the L₁ metric on standard normal data, we have a variance (Eq 44) that grows on the order of p. The distances between points in high-dimensional uniform data become more widely dispersed with this metric. The summary of moment estimates given in this section (Eqs 43 and 44) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 3).

3.2.3 Distribution of one-dimensional projection of pairwise distance onto an attribute

In nearest-neighbor distance-based feature selection like NPDR and Relief-based algorithms, the one-dimensional projection of the pairwise distance onto an attribute (Eq 2) is particularly fundamental to feature quality for association with an outcome. For instance, this distance projection is the predictor used to determine beta coefficients in NPDR. In particular, understanding distributional properties of the projected distances is necessary for defining pseudo P values for NPDR. In this section, we summarize the exact distribution of the one-dimensional projected distance onto an attribute $$ a\in \mathcal{A}$$. These results apply to continuous data, such as gene expression.

In previous sections, we derived the exact density function (Eq 17) and moments (Eqs 18 and 19) for the distribution of $$ Z_a^q={|X_{ia}-X_{ja}|}^q$$. We then derived the exact density (Eq 25) and moments (Eqs 26 and 27) for standard normal data. Analogously, we formulated the exact density (Eq 34) and moments (Eqs 36 and 37) for standard uniform data. From these exact densities and moments, we simply substitute q = 1 to define the distribution of the one-dimensional projected distance onto an attribute $$ a\in \mathcal{A}$$.

Assuming data is standard normal, we substitute q = 1 into the density function of $$ Z_a^q$$ (Eq 25) to arrive at the following density function

The mean corresponding to this Generalized Gamma density is computed by substituting q = 1 into the formula for the mean of $$ Z_a^q$$ (Eq 26). This result is given by

Substituting q = 1 into Eq 27 for the variance, we have the following

These last few results (Eqs 45–47) provide us with the distribution for NPDR predictors when the data is from the standard normal distribution. We show density curves for q = 1, 2, …, 5 for the one-dimensional projection for standard normal data (S22 A Fig in S1 File).

If we have standard uniform data, we substitute q = 1 into the density function of $$ Z_a^q$$ (Eq 34) to obtain the following density function

The mean corresponding to this Kumaraswamy density is computed by substituting q = 1 into the formula for the mean of $$ Z_a^q$$ (Eq 36). After substitution, we have the following result

Substituting q = 1 into the formula for the variance of $$ Z_a^q$$ (Eq 37), we have the following

In the event that the data distribution is standard uniform, the density function (Eq 48), the mean (Eq 49), and the variance (Eq 50) sufficiently define the distribution for NPDR predictors. As in the case of NPDR predictors for standard normal data, we show density curves for q = 1, 2, …, 5 for the NPDR predictor distribution for standard uniform data (S22 B Fig in S1 File).

The means (Eqs 46 and 49) and variances (Eqs.47 and 50) come from the exact distribution of pairwise distances with respect to a single attribute $$ a\in \mathcal{A}$$. This is the distribution of the so-called “projection” of the pairwise distance onto a single attribute to which we have been referring, which is a direct implication from our more general derivations. In a similar manner, one can substitute any value of q ≥ 2 into the general densities of $$ Z_a^q$$ for standard normal (Eq 25) and standard uniform (Eq 34) to derive the associated density of $$ Z_a^q={|X_{ia}-X_{ja}|}^q$$ for the given data type.

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.

3.3.1 Standard normal data

Substituting q = 2 into the asymptotic formula of the mean (Eq 30), we have the following for expected L₂ distance between two independently sampled instances $$ i,j\in \mathcal{I}$$ in standard normal data

In the case of L₂ on standard normal data, we see that the mean of $$ D_{ij}^{\left(2\right)}$$ (Eq 51) grows on the order of $$ \sqrt{p}$$. Hence, the Euclidean distance does not increase as quickly as the Manhattan distance on standard normal data.

Substituting q = 2 into the formula for the asymptotic variance of $$ D_{ij}^{\left(2\right)}$$ (Eq 30) leads to the following

Surprisingly, the asymptotic variance (Eq 52) is just 1. Regardless of data dimensions m and p, the variance of Euclidean distances on standard normal data tends to 1. Therefore, most instances are contained within a ball of radius 1 about the mean in high feature dimension p. This means that the Euclidean distance distribution on standard normal data is simply a horizontal shift to the right of the standard normal distribution.

For the case in which the number of attributes p is small, we have an improved estimate of the mean (Eq 9). The lower dimensional estimate of the mean is given by

For high dimensional data sets like gene expression [20, 21], which typically contain thousands of genes (or features), it is clear that the magnitude of p will be sufficient to use the standard asymptotic estimate (Eq 51) since $$ \sqrt{2p}\approx \sqrt{2p-1}$$ in that case. The summary of moment estimates given in this section (Eqs 52 and 53) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 3).

3.3.2 Standard uniform data

Substituting q = 2 into the asymptotic formula of the mean (Eq 40), we have the following for expected L₂ distance between two independently sampled instances $$ i,j\in \mathcal{I}$$ in standard uniform data

As in the case of standard normal data, the expected value of $$ D_{ij}^{\left(2\right)}$$ (Eq 54) grows on the order of $$ \sqrt{p}$$.

Substituting q = 2 into the formula for the asymptotic variance of $$ D_{ij}^{\left(2\right)}$$ (Eq 40) leads to the following

Once again, the variance of Euclidean distance surprisingly approaches a constant.

For the case in which the number of attributes p is small, we have an improved estimate of the mean (Eq 9). The lower dimensional estimate of the mean is given by

We summarize the moment estimates given in this section for standard L_q metrics (Eqs 55 and 56) organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 3). In the next section, we extend these results for the standard L_q metric to derive asymptotics for the attribute range-normalized (max-min) L_q metric used frequently in Relief-based algorithms [1, 3] for scoring attributes. These derivations use extreme value theory to handle the maximum and minimum attributes for standard normal and standard uniform 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 $$ {\mathcal{F}}_X$$ is said to be degenerate if its density function f_X is the Dirac delta δ(x − c₀) centered at a constant $$ c_0\in \mathbb{R}$$, with corresponding distribution function F_X defined as

Theorem 4.1 (Fisher-Tippett-Gnedenko) Let $$ X_{1a},X_{2a},\dots ,X_{ma}\stackrel{iid}{\sim }{\mathcal{F}}_X({\mu }_x,{\sigma }_x^2)$$ and let $$ {\displaystyle X_a^{\text{max}}=\underset{k\in \mathcal{I}}{max}\left\{X_{ka}\right\}}$$. If there exists two non-random sequences b_m > 0 and c_m such that

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

Using more precise notation, the distribution function of the sample maximum in standard normal data is

Differentiating the distribution function (Eq 60) gives us the following density function for the distribution of the maximum

The distribution of the sample minimum, $$ X_a^{\text{min}}$$, can be derived as follows

With more precise notation, we have the following expression for the distribution function of the minimum

Differentiating the distribution function (Eq 63) gives us the following density function for the distribution of sample minimum

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

The second raw moment of the distribution of sample maximum is derived similarly as follows

Using the first (Eq 65) and second (Eq 66) raw moments of the distribution of sample maximum, the variance is given by

Moving on to the distribution of sample minimum, the first raw moment is given by the following

Similarly, the second raw moment of the distribution of sample minimum is given by the following

Using the first (Eq 68) and second (Eq 69) raw moments of the distribution of sample minimum, the variance is given by

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

For a data distribution whose density is an even function, the expected attribute range (Eq 71) can be simplified to the following expression

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

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

Let $$ {\mu }_{D_{ij}^{\left(q\right)}}$$ and $$ {\sigma }_{D_{ij}^{\left(q\right)}}^2$$ (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

The variance of the max-min normalized distance (Eq 58) distribution is given by the following

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

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

A similar substitution gives us the following expression for the variance of the max-min normalized distance distribution

Therefore, the asymptotic distribution of the max-min normalized distance distribution (Eq 77) becomes

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 $$ c_m=-{\Phi }^{-1}\left(\frac{1}{m}\right)$$ and $$ b_m=\frac{1}{c_m}$$, where Φ is the standard normal cumulative distribution function. Using Taylor’s Theorem, we have the following expansion

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

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

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

which is the cumulative distribution function of the standard Gumbel distribution. The mean of this distribution is given by the following

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

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

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

Therefore, the mean of the range of m iid standard normal random variables is given by

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

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

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

where m is the size of the sample from which the maximum is derived, $$ {\mu }_{\text{max}}^{\left(1\right)}$$ is the median of the sample maximum (Eq 86), $$ {\mu }_{D_{ij}^{\left(q\right)}}$$ is the expected L_q pairwise distance (Eq 28), and $$ {\sigma }_{D_{ij}^{\left(q\right)}}^2$$ 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).

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 ($$ \mathcal{N}(0,1)$$) and standard uniform ($$ \mathcal{U}(0,1)$$) data are given. The cumulative distribution function of the standard normal distribution is represented by Φ. Furthermore, $$ {\mu }_{\text{max}}^{\left(1\right)}\left(m\right)$$ (Eq 86) is the asymptotic median of the sample maximum from m standard normal random samples.

4.1.2 Standard uniform data

Standard uniform data does not have an even density function. Due to the simplicity of the density function, however, we can derive the distribution of the maximum and minimum of a sample of size m explicitly. Using the general forms of the distribution functions of the maximum (Eq 60) and minimum (Eq 63), we have the following distribution functions for standard uniform data

and

where m is the size of the sample from which extremes are derived.

Using the general forms of the density functions of the maximum (Eq 61) and minimum (Eq 64), we have the following density functions for standard uniform data

and

where m is the size of the sample from which extremes are derived.

Then the expected maximum and minimum are computed through straightforward integration as follows

and

where m is the size of the sample from which extremes are derived.

We can compute the second moment about the origin of the sample range as follows

where m is the size of the sample from which extremes are derived.

Using the general asymptotic distribution of max-min normalized distances for any data type (Eq 77) and the mean and variance (Eq 40) of the standard L_q distance metric (Eq 1), we have the following asymptotic estimate for the max-min normalized distance distribution for standard uniform data

where m is the size of the sample from which extremes are derived, $$ {\mu }_{D_{ij}^{\left(q\right)}}$$ is the expected value (Eq 38) of the L_q metric (Eq 1) in standard uniform data, and $$ {\sigma }_{D_{ij}^{\left(q\right)}}^2$$ is the variance (Eq 39) of the L_q metric (Eq 1) in standard uniform data. The summary of moments of the max-min normalized L_q distance metric in standard uniform data (Eq 92) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

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 $$ q\in \mathbb{N}$$, 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.2.1 Standard normal data

Substituting q = 1 into the asymptotic formula for the expected max-min normalized distance (Eq 92), we derive the expected normalized Manhattan distance in standard normal data as follows

where $$ {\mu }_{\text{max}}^{\left(1\right)}\left(m\right)$$ is the expected attribute maximum (Eq 86), m is the size of the sample from which the maximum is derived, and p is the total number of attributes.

Similarly, the variance of $$ D_{ij}^{(1*)}$$ is given by

where $$ {\mu }_{\text{max}}^{\left(1\right)}\left(m\right)$$ is the expected attribute maximum (Eq 86), m is the size of the sample from which the maximum is derived, and p is the total number of attributes. Similar to the variance of the standard Manhattan distance, the variance of the max-min normalized Manhattan distance is on the order of p for fixed instance dimension m. For fixed p, the variance (Eq 102) vanishes as m grows without bound. If we fix m, the same variance increases monotonically with increasing p. The summary of moments derived in this section (Eqs 101 and 102) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

4.2.2 Standard uniform data

Substituting q = 1 into the asymptotic formula for the expected max-min pairwise distance (Eq 100), we derive the expected normalized Manhattan distance in standard uniform data as

where m is the size of the sample from which extremes are derived and p is the total number attributes.

Similarly, the variance of $$ D_{ij}^{(1*)}$$ is given by

where m is the size of the sample from which extremes are derived and p is the total number of attributes. Interestingly, the variance of the max-min normalized Manhattan distance in standard uniform data approaches p/18 as m increases without bound for a fixed number of attributes p. This is the same asymptotic value to which the variance of the standard Manhattan distance (Eq 43) converges. Therefore, large sample sizes make the variance of the normalized Manhattan distance approach the variance of the standard Manhattan distance in standard uniform data. The summary of moments derived in this section (Eqs 103 and 104) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

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).

4.3.1 Standard normal data

Substituting q = 2 into the asymptotic formula for the expected max-min normalized pairwise distance (Eq 92), we derive the expected normalized Euclidean distance in standard normal data as

where $$ {\mu }_{\text{max}}^{\left(1\right)}\left(m\right)$$ is the expected attribute maximum (Eq 86), m is the size of the sample from which the maximum is derived, and p is the total number of attributes.

Similarly, the variance of $$ D_{ij}^{(2*)}$$ is given by

where $$ {\mu }_{\text{max}}^{\left(1\right)}\left(m\right)$$ is the expected attribute maximum (Eq 86) and m is the size of the sample from which the maximum is derived. It is interesting to note that the variance (Eq 106) vanishes as the sample size m increases without bound, which means that all distances will be tightly clustered about the mean (Eq 105). This is different than the variance of the standard L₂ metric (Eq 52), which is asymptotically equal to 1. This could imply that any two pairwise distances computed with the max-min normalized Euclidean metric in a large sample space m may be indistinguishable, which is another curse of dimensionality. The summary of moments derived in this section (Eqs 105 and 106) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

4.3.2 Standard uniform data

Substituting q = 2 into the asymptotic formula for the expected max-min normalized pairwise distance (Eq 100), we derive the expected normalized Euclidean distance in standard uniform data as

where m is the size of the sample from which extremes are derived and p is the total number of attributes.

Similarly, the variance of $$ D_{ij}^{(2*)}$$ is given by

where m is the size of the sample from which extremes are derived. Similar to the variance of max-min normalized Manhattan distances in standard uniform data (Eq 104), the variance of normalized Euclidean distances approaches the variance of the standard Euclidean distances in uniform data (Eq 55) as m increases without bound. That is, the variance of the max-min normalized Euclidean distance (Eq 108) approaches 7/120 as m grows larger. The summary of moments derived in this section (Eqs 107 and 108) is organized by metric, data type, statistic (mean or variance), and asymptotic formula (Fig 4).

We summarize moment estimates in figures (Figs 2–4) that contain all of our asymptotic results for both standard and max-min normalized L_q metrics in each data type we have considered. This includes our most general results for any combination of sample size m, number of attributes p, type of metric L_q, and data type (Fig 2). From these more general derivations, we show the results of the standard L₁ and L₂ metrics for any combination of sample size m, number of attributes p, and data type (Fig 3). Our last set of summarized results show asymptotics for the max-min normalized L₁ and L₂ metrics for any combination of sample size m, number of attributes p, and data type (Fig 4). For both standard and max-min normalized L₂ metrics (Figs 3 and 4), the low-dimensional improved estimates of sample means (Eqs 53 and 56) are used because they perform well at both low and high attribute dimension p.

In the next section, we make a transition into discrete GWAS data. We will discuss some commonly known metrics and then a relatively new metric, which will lead us into novel asymptotic results for this data type.

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

Then the expected pairwise GM distance between instances $$ i,j\in \mathcal{I}$$ is given by

The second moment about the origin for the GM distance is computed as follows

Using the first (Eq 117) and second (Eq 118) raw moments of the GM distance, the variance is given by

With the mean and variance estimates (Eqs 117 and 119), the asymptotic GM distance distribution is given by the following

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

Using the expected AM attribute diff (Eq 121), the expected pairwise AM distance (Eq 114) between instances $$ i,j\in \mathcal{I}$$ is given by

The second moment about the origin for the AM distance is computed as follows

Using the first (Eq 122) and second (Eq 123) raw moments of the asymptotic AM distance distribution, the variance is given by

With the mean (Eq 122) and variance (Eq 124) estimates of AM distances, the asymptotic AM distance distribution is given by the following

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 $$ \mathcal{B}(2,f_a)$$ for all $$ a\in \mathcal{A}$$. 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 $$ i,j\in \mathcal{I}$$ 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

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

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

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

Also using the sum-to-one constraint (Eq 126) and the Ti/Tv ratio constraint (Eq 127), it is clear that we have $$ \text{P}\left(\text{Tv}\right)=\frac{1}{\eta +1}$$ and $$ \text{P}\left(\text{Ti}\right)=\frac{\eta }{\eta +1}$$. Without loss of generality, we then sample

Then it immediately follows that we have

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 $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=k]$$ for each $$ k\in \mathcal{D}=\{0,\frac{1}{4},\frac{1}{2},\frac{3}{4},1\}$$. Let y represent a random sample of size p from {0, 1, 2}, where

We derive $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=0]$$ as follows

We derive $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=\frac{1}{4}]$$ as follows

We derive $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=\frac{1}{2}]$$ as follows

We derive $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=\frac{3}{4}]$$ as follows

We derive $$ \text{P}[{\text{d}}_{ij}^{\text{TiTv}}\left(a\right)=1]$$ as follows

Using the TiTv diff probabilities (Eqs 133–137), we compute the expected TiTv distance between instances $$ i,j\in \mathcal{I}$$ as follows

The second moment about the origin for the TiTv distance is computed as follows

Using the first (Eq 138) and second (Eq 139) raw moments of the TiTv distance, the variance is given by

With the mean (Eq 138) and variance (Eq 140) estimates, the asymptotic TiTv distance distribution is given by the following

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

The maximum TiTv distance occurs at $$ {\overline{f}}_a=0.5$$ 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 ($$ {\overline{f}}_a\to 0$$), the predicted TiTv distance approaches 0. The same is true after the minor allele switches ($$ {\overline{f}}_a\to 1$$). To explore how TiTv distance changes with increased minor allele frequency, we fixed the Ti/Tv ratio η and generated simulated TiTv distances for $$ {\overline{f}}_a=0.055,0.150,0.250,\text{and}0.350$$ (Fig 7A). For fixed η, TiTv distance increases significantly with increased $$ {\overline{f}}_a$$. We similarly fixed the average minor allele frequency $$ {\overline{f}}_a$$ 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.

Fig 6

Predicted average TiTv distance as a function of average minor allele frequency $$ {\overline{f}}_a$$ (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.

We also compared theoretical and sample moments as a function of η = Ti/Tv and $$ {\overline{f}}_a$$ for the TiTv distance metric (Fig 7B and 7D). We fixed $$ {\overline{f}}_a$$ 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 $$ {\overline{f}}_a$$ (Fig 7D). In this case, there is approximate agreement with simulated and theoretical moments as $$ {\overline{f}}_a$$ increases.

Fig 7

Density curves and moments of TiTv distance as a function of average MAF $$ {\overline{f}}_a$$, 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 $$ {\overline{f}}_a=0.055$$, 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 $$ {\overline{f}}_a$$. TiTv distance increases as $$ {\overline{f}}_a$$ 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 $$ {\overline{f}}_a$$. Distance increases as the number of minor alleles increases. Theoretical and simulated moments are approximately the same.

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).

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 $$ X_{ia}\sim \mathcal{B}(2,f_a)$$, where f_a for all $$ a\in \mathcal{A}$$ 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).

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, $$ \text{P}[{\text{d}}_{ij}^{\text{GM}}\left(a\right)=k]$$, 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

Similarly, the probability that the GM diff is equal to 1 is derived as follows

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

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

The variance of the GM diff metric is given by

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

The probability of the AM diff metric being equal to 1/2 is computed similarly as follows

Finally, the probability of the AM diff metric being equal to 1 is given by the following

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

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

The variance of the AM diff metric is given by

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

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

The variance of the TiTv diff metric is given by

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

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

The variance can be esimated with the following

Let $$ {\mu }_{D_{ij}^{\text{fMRI}}}$$ and $$ {\sigma }_{D_{ij}^{\text{fMRI}}}^2$$ 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

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 $$ k\ne \mathcal{A}$$. This is done as follows

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

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

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 $$ a\in \mathcal{A}$$, so the cross-covariance between the magnitude differences $$ |{\widehat{A}}_{ak}^{\left(i\right)}-{\widehat{A}}_{ak}^{\left(j\right)}|$$ for different pairs of ROIs (a and k ≠ a) is negligible here. When considering all ROIs $$ a\in \mathcal{A}$$, 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

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

Similarly, the variance of $$ D_{ij}^{\text{fMRI}*}$$ is given by

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.

Fig 10

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

8.1 Continuous data

Without loss of generality, suppose we have X^(m×p) where $$ X_{ia}\sim \mathcal{N}(0,1)$$ 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

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) $$ {\overline{r}}_{\text{abs}}=0.105,0.263,0.458,\text{and}0.612$$. (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 $$ f_a\text{for}\text{all}a\in \mathcal{A}$$. (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).

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

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 $$ f_a\text{for}\text{all}a\in \mathcal{A}$$. Each attribute $$ a\in \mathcal{A}$$ 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 $$ {\overline{r}}_{\text{abs}}$$ 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 $$ {\overline{r}}_{\text{abs}}$$. We introduced correlation to the transformed data matrix (Fig 9) with the cholesky method used previously.