{'fraction_non_alphanumeric': 0.03672124550416258, 'fraction_numerical': 0.00955758444628889, 'mean_word_length': 4.590551181102362, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On minimizers and convolutional filters: a partial justification for the effectiveness of CNNs in categorical sequence analysis

Minimizers and convolutional neural networks (CNNs) are two quite distinct popular techniques that have both been employed to analyze categorical biological sequences. At face value, the methods seem entirely dissimilar. Minimizers use min-wise hashing on a rolling window to extract a single important k-mer feature per window. CNNs start with a wide array of randomly initialized convolutional filters, paired with a pooling operation, and then multiple additional neural layers to learn both the filters themselves and how those filters can be used to classify the sequence. In this manuscript, we demonstrate through a careful mathematical analysis of hash function properties that for sequences over a categorical alphabet, random Gaussian initialization of convolutional filters with max-pooling is equivalent to choosing a minimizer ordering such that selected k-mers are (in Hamming distance) far from the k-mers within the sequence but close to other minimizers. In additional empirical experiments, we find that this property manifests as decreased density in repetitive regions. This provides a partial explanation for the effectiveness of CNNs in categorical sequence analysis.


Introduction
It is a pithy statement now that the near exponential explosion of biological sequence data we confront requires the construction of more efficient tailored algorithms capable of handling the data deluge [29,4]. Over the last decade, several tools have emerged from the algorithmic literature as instrumental for biological sequence analysis, whether in reducing time-or space-complexity. For example, for read-alignment/assembly, compressive data structures that rely on the inherent redundancy of the underlying genome(s), such as the FM-index [15], entropy-scaling search trees [51], and more recently the r-index [20] have been widely used in applications including assembly and read-mapping [44,49,31]. Alternately, probabilistic sketching methods such as MinHash [5], HyperLogLog [17], and HyperMinHash [52] have found great applicability in fast genome comparison and classification [38,3]. Rather than understanding the entropic structure of the underlying data, these methods instead use random hash functions to force the data into a shape with well-characterized approximation error. And finally, local k-mer subsampling schemes such as minimizers [42,40], syncmers [14], and minimally-overlapping words [18] reduce the redundancy found in the overlapping neighboring kmers of a sequence, and thus allow speeding up tasks like taxonomic classification [48], read mapping, or assembly [33]. These methods have all become necessary because although Moore's law on transistor density has continued unabated, the same cannot be said about single-threaded processing times or fast memory access.
However, it bears remarking that even as much of more traditional genomics analysis has turned to increasingly efficient algorithmics, the burgeoning subarea of deep learning in biology has exploded [1,16], and the neural networks being used for the same tasks (such as metagenomic classification) are by comparison less constrained by the need for efficiency. Instead, deep learning is able to continue to tap into Moore's law because their computational primitive of numerical linear algebra is easily vectorized onto hardware accelerators such as GPUs (graphics processing units) and TPUs (tensor processing units) [35,28]. On bioinformatics tasks that map more directly onto traditional ML tasks-such as classification and prediction of images-those models often face little competition from more traditional methods [11,34]. Furthermore, deep learning methods are often able to achieve comparable accuracy even on core computational biology tasks like variant calling [39] and metagenomic binning [50], but to do so require extremely large amounts of computation for both training and inference.
Still, although there are theoretical results showing that with unbounded compute, neural networks can learn any function [23], and hardware accelerators are able to leverage much larger amounts of raw processing power than more conventional algorithmic approaches, a lot of work has been done to create more efficient architectures, including convolutional neural nets (CNNs) [19], recurrent neural nets (RNNs) [41], long-shortterm memory structures (LSTM) [22], Transformer networks [46], and more. Indeed, much of the business of deep learning is in applying putatively more efficient architectures to novel tasks and datasets. Sometimes, neural networks have a biological justification-and indeed, they were originally inspired by simplified models of biological neurons; for example, CNNs were based on the mammalian visual cortex [24]. However, although some ML models have an intuitive justification, often, they are simply found to perform well empirically, and it is difficult to interpret why they work, or what the learned weights might mean biologically [37].
In this manuscript, we focus on understanding the efficacy of CNNs on categorical sequence data. While interpretations of a CNNs weights and neurons are often made by way of comparison to the receptive fields of visual neurons, that interpretation falls apart when applied to biological sequence data. Unlike the brightness of a pixel in an image, biological sequences are not ordinal, but rather instead categorical vectorsa nucleotide is either present or not in a particular position, without any sense of relative magnitude. In images, for example, a filter may detect a horizontal edge, which is characterized by bright pixels on one side and dark on the other; if you slightly brighten the pixels on one side, or add some noise to the image, the edge is still characterized by that pattern, which filters are trained to pick up. However, while you could imagine patterns of nucleotides that correspond to an edge, e.g. AAAATTTT, there are no intermediate 'levels' for a CNN filter to pick up. Still, CNNs have proved effective on genomic data, such as in the classification of metagenomic sequences of bacteria by taxonomy [16]. It thus seems that CNNs are not intuitively suited for categorical sequence classification, but empirically, they irrespectively have excellent performance. Why?
Here, we prove two technical Theorems 2 and 3 showing that the hash family of dot products with random spherical Gaussian multivariates preferentially selects more extremal elements as maximums, but uniformly randomly selects among equally distinct elements, and that maximums are more likely to be similar to each  figure). Those k-mers are hashed-typically randomly hashed-to integers, and the minimum integer within each overlapping window (length 5 in figure) is computed, called the 'minimizer'. Only unique minimizers are stored, giving a sparse representation. (right) Applying a 1D convolutional filter with maxpooling. A vector of values is convolved with a weights vector (here of length 8) to determine the output of a single filter. A max-pooling operation takes the maximums in some window (window size here is 5), and sparsification can be achieved by increasing stride-length. These maximums are features for the remaining layers of a CNN. other. A immediate corollary is then our Main Theorem 1, showing that on categorical sequences, minimizers and untrained randomly initialized convolutional filters with max-pooling ( Figure 1) are nearly equivalent. Theorem 1. Consider a CNN acting on one-hot encoded categorical vectors with a single convolutional filter following by max-pooling, both of stride-1. Then the output of the max-pooling layer is precisely equivalent to choosing a minimizer over the windows/patches that are max-pooled. If the weights of the filter are initialized as a spherical Gaussian multivariate, then the implied minimizer hash function is mostly random but has the following properties: 1. It is at least as likely to choose the the most distinct categorical feature in a window as any other k-mer, where distinctness is measured in absolute Hamming deviation from the other features; 2. And the set of minimizers it chooses overall are likely to be closer in Hamming distance to each other than a random set of k-mers.
We then show in empirical simulations that these properties manifest as decreased density in highly repetitive sequences as compared to random minimizer schemes. Although at least one minimizer is guaranteed to be selected from each window, the number of minimizers that are selected overall determines the density; lowering the density can improve the efficiency of minimizer-based algorithms, as has been a design goal in the minimizer literature [36,53]. Our results show that Gaussian convolutions are better for density than random minimizers, though special-purpose methods such as Miniception [53] still do better than Gaussian convolutions. Together, our theory and experiments resolve our central question by connecting together two seemingly unrelated methods that have both achieved powerful results in computational biology, and explaining some of the advantages of using random Gaussian convolutions for feature selection.

Building blocks
We begin with a review of hashing, permutations, MinHash, minimizers, and CNNs. Note that the primary biological application is to sequence analysis, which is 1-dimensional. Although all of our analyses generalize naturally to higher dimensions (such as a 2D matrix of non-ordinal features), the notation becomes quite confusing; without loss of generality we will focus on the 1D case.
Three key intuitions will be needed: 1. For minimizers and MinHash, the hash functions need only impose an ordering on the domain, and as such need not follow exactly classical hash function constructions. 2. In contrast to MinHash, minimizers do not require min-wise independence of their hash functions. 3. A random convolutional filter followed by max-pooling precisely orders the space of k-mers and chooses an extreme element.

Hashing and permutations
The key to our analysis will be in understanding the role of hashing [8] and permutations. We recall some basic concepts here. For reference, see any standard text or this gentle introduction to fast modern hashing methods by Thorup [45].
Definition 1. A hash function h : U → M maps elements from some universe U to some range M .

Definition 2.
A random hash function h : U → M is a function that is uniformly drawn from a family H of hash functions.
To illustrate, let's start with a classical example. Let F p be the finite field with p elements, for some prime p. Then we can define a hash function h a,b : F p → F p given by h a,b (x) = ax + b mod p. The hash family here is parameterized by a, b ∈ F p , and so our analysis can operate on probabilities and expectations that arise from treating a, b, and therefore h a,b , as random variables. Another more sophisticated modern example is the vector multiply-shift family of hash functions, introduced by Dietzfelbinger, designed to hash vectors to scalars without making use of finite field arithmetic [12]. We introduce it here because the construction is mathematically equivalent to a dot product with uniform random integers in the integer ring, followed by an integer division/bit-shift operation.
We will needw ≥ w + l − 1, and then we pick a uniform random vector a ∈ [2w] d , as well as a uniform random element b ∈ [2w]. We define a hash function where the dot product and addition are in the ring [2w], and div is ordinary integer division without remainder (i.e. a bit-shift to the right byw − l bits), leaving an answer that is just l bits. In practice, using fast 64-bit integer arithmetic, we can let l = 32, w = 32, and w = 64, allowing us to hash vectors of unsigned 32-bit integers by doing a dot product with a random 64-bit integer vector, adding another random 64-bit integer, and then taking the higher 32-bits.
Depending on the application at hand, different properties of a hash function may be desirable, such as universality [8], strong universality, k-independence [47], or min-wise independence [6]. Both of the examples given above exhibit strong universality (also known as 2-independence).

Definition 3.
H is a strongly universal (or 2-wise independent) hash family if ∀i 1 = i 2 ∈ U , and ∀j 1 , j k ∈ M , Roughly speaking, any two hash values can be construed as independent uniform random variables on the range. However, in this work, we are primarily interested in permutations. Nontrivial permutations are expensive to encode, but they can be approximated via random hashing. This is the basis of the celebrated MinHash algorithm for computing set similarity [5]. Note that for any set S ⊂ U with no collisions under a hash function h-i.e. h(s i ) = h(s j ) for any s i = s j ∈ S-the hash function defines an ordering/permutation on S. One property of random permutations people have sought to capture is that every item in S has an equal chance of being the smallest, which we can formalize.
Min-wise independence unfortunately does not follow as a consequence of strong universality, though you can approximate it with sufficiently high degrees of k-independence [25] or by using a twisted variant of tabulation hashing [10]. Alternately, many real-world implementations eschew the formal guarantees of random hashing, and instead just use a deterministic hash function-such as Murmurhash3 [2], the SHA family of cryptographic hash functions [13], or efficient canonical choices of group generators in prime fields. This is very common in bioinformatics software making use of minimizers. However, such constructions obscure the connections we will be drawing in this paper.

Min-wise hashing
Let's begin with min-wise hashing (MinHash), which can be thought of as a randomized global feature selection method over the space of k-mers in a sequence, and which is closely related to the local feature selection method of minimizers. MinHash was invented for computing the resemblance of documents as given by the Jaccard index of k-mers (or n-grams or shingles) [5], so it gives a quite strong promise about the features it selects.
Definition 5. Given two sets A and B, the Jaccard index [26] is MinHash relies on a random permutation of the set A ∪ B.
Lemma 1. Given a min-wise independent hash function h and two sets A, B, Proof. The lemma follows directly from Definition 4 because every item has in the union has equal probability of being the minimum.
A set A can then be represented for computing Jaccard index by storing just the minimum item (or its hash value). The error in Jaccard index estimation can then be driven down by a factor of 1 √ m by repeating with m independent permutations and averaging. Alternately, the error can also be driven down by using a single permutation and keeping the smallest m items [9]. MinHash is great for comparing entire sequences globally against each other [38], and one hope would be that we can modify MinHash to being a local feature selection method. That goal is effectively achieved through minimizers, though as a historical note, minimizers were invented independently of MinHash.

Minimizers
Minimizers [42,40] are a local k-mer selection scheme, in some ways, the classic k-mer selection scheme. The most important feature of a local k-mer selection scheme is translation invariance; we want to subsample the set of k-mers in a sequence in such a way that even if we insert or delete a letter at the beginning of the sequence, the set of minimizers does not change very much. There are a number of more modern k-mer selection schemes [14,18,43], with slightly different properties, but minimizers were among the first used in computational biology.
Minimizers are related to min-wise hashing [5], but instead of getting features for an entire sequence at once, they break up a sequence into smaller windows and get the minimum hash within each window. That minimum k-mer, a minimizer, is used to match the sequence to some reference, e.g. for classification [48] or for sequence assembly/mapping [33]. Often, for longer sequences, we match the sequence to a reference only if multiple minimizers from different windows match. The compressive nature of minimizers appears because most of the time, the minimizer remains constant as the window rolls, so the total number of minimizers for a sequence is much smaller than the total number of windows. Indeed, one of the key metrics considered for minimizer schemes is the density, defined as the fraction of all k-mers in a sequence that are selected.
Let's more precisely state a few standard results. Consider an alphabet Σ. For genomics, Σ = {A, C, G, T }, whereas for protein sequences |Σ| = 20 in the standard amino acid alphabet. We are interested in analyzing the set of variable-length strings where each x i ∈ Σ, one common analytical technique is to consider all length-k substrings {k 0 , . . . , k l−k }, where k i = x i · · · x i+k−1 ∈ Σ k . Given a hash function h, instead of constructing a MinHash sketch by taking the smallest k-mers overall, we instead define the minimizers of the sequence as {w 0 , . . . , w l−k−w }, where Lemma 2. Let l > w, and let x ∈ Σ l be any string of length l without duplicate k-mers. Then using the notation given above, if h is a min-wise independent hash function, then adjacent windows share a minimizer with probability Pr h (w i = w i+1 ) ≥ w−1 w+1 .
Proof. Adjacent windows share w − 1 k-mers, and there are w + 1 unique k-mers between the two windows. Thus, the Jaccard index is precisely w−1 w+1 , and the proof follows from Lemma 1.
Proof. As before, there are w + 1 unique k-mers between two adjacent windows. The very first k-mer belongs only to the earlier window, and the last k-mer belongs only to the later window. When iterating across windows, a new minimizer is selected precisely when either the new (last) k-mer is the smallest (and thus the new minimizer) or when the first k-mer is the smallest (so it was the previous minimizer, and a new minimizer needs to be selected). Thus, on iterating to each new window, the probability of selecting a new minimizer is 2 w+1 , finishing the proof.
Thus, the deduplicated set of minimizers of a sequence is much fewer than l − k − w. However, a key difference between minimizers and MinHash is that the hash function need not actually be min-wise independent in general. This is because we are not using minimizer-collision probabilities as an estimator for Jaccard index, but rather simply using them as a sparse sampling of the k-mer space. Minimizers only require translation invariance, which is satisfied by any arbitrary permutation, rather than needing a random permutation. Indeed, this fact has been exploited to construct non-uniformly-random minimizers that are more evenly distributed, or that are likely to be rarer in a genome [53,27]. These works can reduce the density from the 2/(w + 1) of random minimizers [42] to for example 1.67/(w + 1) using the Miniception construction scheme [53].
Of course, some amount of randomness is important; in the worst case, an adversarially chosen permutation that orders k-mers in the same order as appears in the sequence gives no amount of subsampling. Or, more realistically, simply taking a lexicographic ordering on the space of k-mers works quite badly, for example, on poly-A strings where the repetitiveness of the poly-A prefix causes many distinct k-mers to be minimizers of adjacent windows, increasing density, which is bad. One of the main empirical results of this manuscript is that for minimizer schemes based on random Gaussian convolutional filters, repetitiveness actually helps decrease density, improving rather than hurting performance.

CNNs
CNNs are inspired by the visual cortex of mammals, and were notably demonstrated to be effective for image processing [24,19]. CNNs are characterized by applying a set of filters in a translation-invariant noiserobust way to different parts of an image to generate a set of features, adding a pooling layer to reduce the information passed downstream, and then following up with a feed-forward neural network for analyzing the features and connecting them to a classification or prediction [32]. Of course, this is a gross oversimplification, and modern architectures are much more complex, but this captures the basic idea.
For our analysis, we consider a simple 1D-CNN on a 4-letter alphabet Σ with an initial convolutional layer with a single filter of size k and stride-1, a max-pooling layer with patch-size w and stride-1, followed up by an arbitrary feed-forward neural network-consider a multi-layer perceptron for simplicity, but it is irrelevant for our analysis-and initialized with Gaussian random weights with mean 0 and variance 1. The results that follow generalize naturally to other finite alphabets, multiple filters, and multiple dimensions, but the analysis will be easier in this setup.
More formally, let s = [s 0 , . . . , s l−l ] ∈ Σ l be a length-l string. Encode the string s in a one-hot encoding e = e(s) = [e 0 , . . . , e 4l−1 ] ∈ {0, 1} 4l . Our convolutional filter g is initialized as a spherical Gaussian multivariate vector with i.i.d. components of length 4k, g = [g 0 , . . . , g 4k−1 ]. Because our one-hot encoding expanded the length of the vector by a factor of 4, we will be using a stride of 4 instead of 1-we eschew tensor notation for the sake of simplicity. Then, the first convolutional 3 layer is the function L 1 : {0, 1} 4l → R l−k given by The second layer of of the CNN is the max-pooling function, given by L 2 : R l−k → R l−k−w as After the max-pooling layer, the remainder of the neural network is trained to use the outputted features for the designated classification or prediction task. It should be apparent that the setup for convolutional filters closely resembles that of the setup for minimizers, where the 'hash function' is a dot product with the weights vector. In both cases, some function is applied to k-mers in the string on a rolling basis. Then, we keep the extreme value of the output of that function, whether it is a minimum or maximum, and pass that onto further analytical pipelines. We address below why convolutional filters work on categorical sequences, when the usual story told is about robustness to non-categorical (ordinal/interval/ratio) noise in feature selection.

Proofs
Recall that the vector-multiply-shift family of hash functions defined by dot product with a uniform random ring element, following by division without remainder, is 2-independent. Roughly speaking, our main claim is that the family of hash functions defined by dot product with a multivariate spherical Gaussian has the property that equally distinct k-mers are equally likely to be selected as minimizers/maximizers, and more distinct k-mers are more likely to be selected as minimizers/maximizers, but the set of minimizers/maximizers selected tends to be similar to each other.
To make this rigorous, we first need to know what we mean by the 'distinctness' of a k-mer. We define that by the total (summed) Hamming distance from all the other unique k-mers in a set; this is basically the absolute deviation of the k-mer from the set. We will call this the 'degree' of the k-mer in the set-consider a graph with k-mers as vertices and edge weights corresponding to the Hamming distance. Our first goal is to show that the degree of a k-mer determines it's likelihood of being either the minimum or maximum under the Gaussian convolution hash family. Later we will also show that extrema also correlated in composition, so the overall set of selected k-mers is similar to each other.
Because we are considering convolution with a multivariate spherical Gaussian, we can take advantage of a large body of literature on manipulating i.i.d. Gaussians. However, we must first rewrite a k-mer in a one-hot encoding so that convolution with a multivariate Gaussian is well-defined (otherwise, what does it mean to multiply a nucleotide "C(ytosine)" with a real number). Given these preliminaries, we are now able to state our theorem.
Proof. The naive approach would be to try to directly prove that h(x) is likely to be greater than h(y). Unfortunately, this approach fails: because Gaussians are symmetric about 0, E(x·g−y·g) = (x−y)·Eg = 0. Instead, in this proof we will focus on variances.
Let's order all the elements of S and place x and y as the first two elements to make notation easier. That is to say, without loss of generality, let S = {x = s 1 , y = s 2 , s 3 , . . . , s n }. Let the random variable Y i = h(s i ), and let ∆ i = ∆(s i ), the degree.
First, we're going to relate the degree of an element to the square of its hash's deviation from all the other hashed values.
Proof. Each Y i is a sum of 1D Gaussians from g, so Y i − Y j precisely cancels out any shared terms, leaving us with positive copies of the Gaussians only in Y i , and negative copies of the Gaussians only in Y j . Because all our binary vectors had the same number of set bits, the total number of both positive and negative Gaussians that are summed to form Y i − Y j is precisely the Hamming distance ||s i − s j || 1 . Since we canceled out any shared terms, all the remaining Gaussians are i.i.d., and due to the symmetry of a Gaussian under reflection, that means that we have that many independent Gaussians. The sum of t independent N (0, 1) Gaussians is just another Gaussian with distribution N (0, t) (i.e. a variance-t Gaussian), and the second moment of a Gaussian is just its variance. Thus, E(Y i − Y j ) 2 = ||s i − s j || 1 , and the lemma follows by linearity of expectation.
Interpreting Lemma 4, the degree ∆ i gives the expected squared deviation after the dot product. Arguing solely from expectations, we expect the lowest degree items to have the lowest squared deviation after the dot product, and therefore be closest to the mean. Conversely, high degrees correspond to being further away from the mean, and the set member that has the highest squared deviation from the mean has to be either the min or the max. The joint distribution is symmetric about the origin, so the probability of being the min or the max are equal. Thus, we need only show that with probability at least 0.5, Y 1 has as high of a squared deviation as Y 2 .
We now define a new random variable by the difference of the squared deviations When Z ≥ 0, Y 1 has at least as high of squared deviation as Y 2 , and vice versa when Z ≤ 0. Of course, EZ = ∆ 1 − ∆ 2 ≥ 0, but expectation is insufficient for showing that with probability 0.5, Z ≥ 0. That is thus the goal for the remainder of this proof. As in the proof of Lemma 4, we use the fact that the Y i 's arise as sums of selected Gaussians from g = {g 1 , . . . , g d }. Let t = ||s i − s j || 1 , which is even because all the bit vectors have the same number of set bits. Then (Y i − Y j ) is the sum of t/2 entries from g minus the sum of another distinct t/2 entries from g, which we can write as Then (Y i − Y j ) 2 is the sum of t squared Gaussians and all of the cross terms, which are either positive or negative copies of products of two independent Gaussians (for notational simplicity, we did not bother writing out which copies are positive or negative): Summing everything together, we can rewrite where the c i 's and c i,j 's are unknown positive or negative integer coefficients. Note that we get nontrivial coefficients because although within (Y i − Y j ) all the component Gaussians are unique, this is no longer true when summing everything together. The signs of the c i,j 's do not matter. For i.i.d. Gaussians g i and g j , we can rewrite which is just the difference of two independent parameter-1 χ 2 variables with the same distribution. The difference of two mutually independent random variables of the same distribution is always symmetric about the origin-in this case, the difference of two independent χ 2 variables gives a variance-gamma distribution [30]. Thus, the right term d i=1 d j=i+1 c i,j g i g j of equation 14 is symmetric about the origin. Additionally, using Eg 2 i = 1 and i can be represented as a sum of a bunch of positive and negative copies of parameter-1 χ 2 variables of the same distribution-we have c i copies g 2 i , which is a parameter-1 χ 2 variable-with at least as many positive as negative copies. Because each negative χ 2 variable is pairwise independent of every positive variable, we can pair each negative copy with an independent positive copy of the same distribution. Using the same logic as above, those pairs when summed are symmetric about the origin (and again variance-gamma distributions).
The only asymmetric part of Z is therefore the leftover χ 2 terms (if any), which are strictly positive. Because Z is the sum of something symmetric about the origin and a strictly positive component, Pr(Z ≥ 0) ≥ 0.5, concluding the proof.
Theorem 3. Consider the universe U of all n binary vectors in {0, 1} d with m set bits. Let g be a spherical multivariate Gaussian random variable of dimension d (each entry g i ∼ N (0, 1) i.i.d.), defining a hash function h : U → R by h(x) = x · g. Letŝ be a (universal) maximizer of U under h, defined by h(ŝ) = max s∈S h(s) ≡ M . Then for any x, y ∈ U such that ||x −ŝ|| 1 < ||y −ŝ|| 1 , Eh(x) > Eh(y), the conditional expectations given thatŝ is a maximizer.
Proof. The proof is elementary; intuition is being correlated with a maximizer makes you larger on average.
First note that the event that there are two distinct maximizers has measure zero, so in this proof we assumeŝ to be unique. The theorem follows as a straight-forward consequence of linearity of expectation, after conditioning on the maximizerŝ-for ease of notation, all expectations in this section are conditional expectations. Consider the conditional expectations of the entries g i . Let's abuse notation and treat bit vectors as sets of indicies; for example, to say that i ∈ x if x i = 1. Then we know two facts: 1. E(g i |i ∈ŝ) = M m , because we have no information to break the symmetry among set bits ofŝ. 2. E(g i |i ∈ŝ) < M m , because otherwise the unique maximizer would not beŝ. Then we can explicitly compute Eh(x) (or respectively Eh(y)) as follows: Then subtracting and substituting in the distance assumption, we get which completes the proof.
We can now directly apply Theorems 2 and 3 to get Theorem 1. A one-hot encoding of a categorical vector precisely gives binary vectors with the same number of set bits. The setup of Theorem 1 follows directly from the definitions set up in Sections and 2.3 and 2.4 and illustrated in Figure 1: convolution with a randomly initialized spherical Gaussian is clearly some kind of hash function, vector-mapped across positions in the sequence (though perhaps not one with the standard properties), and a max-pooling operation is equivalent to taking a minimum across windows. However, we proved in Theorem 2 that a dot-product hash function with spherical Gaussian parameters preferentially selects more distinct k-mers, but is equally likely to select k-mers that are equally distinct. The hash function so defined striates k-mer features by degree (Hamming distance from all other k-mers), and all k-mers of a given degree have the same probability of being chosen as a minimum or maximum, but at least as high a probability as any k-mer of lower degree, proving the first part of Theorem 1. The second part of Theorem 1 is a consequence of the Theorem 3, as we showed that the closer a k-mer is to the universal minimizer, the more likely it is to be selected as a local minimizer.

Experimental Results
While we have proven general properties of using Gaussian convolution as a minimizer selection scheme, our theorems do not say anything about in what situations these behaviors manifest. To address that, we turn to numerical simulation ( Figure 2). The correct interpretation of our theory is that k-mers which are further away (in Hamming distance) from other k-mers in a window, but similar to other minimizers, are more likely to be selected. This phenomenon thus primarily occurs in repetitive sequences, where k-mers within a window are similar to each other. We thus run our experiments on a random repetitive sequence with mutations, similar to modelling tandem repeats of different lengths. We chose a k-mer size of 8 for our experiments, and a total sequence length of 1007 (so that we have 1000 k-mers). We chose a window size of w = 19, as the density of random minimizers is expected to be 2/(w + 1) = 0.1. We then swept over repeat lengths from 1 to 30, with a 10% mutation rate.
We measured three different quantities: (1) average distance from all k-mers, (2) average distance from other minimizers, and (3) the density of the minimizers. The first two quantities correspond to empirical validation of our two technical theorems. Random minimizers and Gaussian convolutions are on average the same distance from all k-mers, asymptotically approaching 6 because 8-mers with a 4-letter alphabet on average share 2 characters; importantly, Theorem 2 says that Gaussian convolutions should be on average far from other k-mers, and this turns out to match random minimizers. However, Gaussian convolutions minimizers are on average much closer to each other than random minimizers are; this is due to Theorem 3.
One seeming consequence is that Gaussian convolution minimizers have lower density in repetitive windows than random minimizers do. Once the repeat length grows to the window size, the density effects disappear entirely, but we see a minimum density as low as 0.0756 = 1.512/(w + 1) when the repeat length is one less than the window size. It is true that random minimizers show a similar lowered density in repetitive windows, but the effect is much more pronounced for Gaussian convolution minimizers. As a caveat, the decreased density is not alone a reason to choose Gaussian convolution minimizers though, as Gaussian convolution minimizer density only decreases for repetitive regions, whereas existing work such as Miniception allows a consistent lowered density of around 1.67/(w+1) over both repetitive and non-repetitive regions [53]. Instead, these experiments are meant simply to partially explain the performance of convolutional filters.
All of the code used to run our experiments and generate Figure 2 are available on Github: https://github.com/yunwilliamyu/gaussian-minimizer-density

Discussion
As discussed earlier, minimizers and CNN features do not depend on more classical notions of uniform hashing. Indeed, this idea has been independently explored for both minimizers and CNNs. On the minimizer front, there are modifications to the hash function for better density [53] or postprocessing the permutation using inverse document/genome frequency [27]. For CNNs, feature construction is largely trained, instead of designed, but there is also work specifically on architectures for promoting better features [7]. Here we show that just initializing with Gaussian weights causes some correlation to distinctiveness, a proxy for inverse frequency related to density in repetitive regions. Notably, clusters of similar data are mapped close together with a Gaussian convolution, which does not happen for random minimizers. This is a known property of CNN filters when it comes to ordinal data, and we show it remains true for categorical data. In biological terms, all k-mers matched by a spaced seed get mapped close to each other by a Gaussian convolution. This highlights one of the potential ramifications of this paper: it may be possible to design or train convolutional filters that explicitly learn some specific minimizer hash function of interest, rather than just Fig. 2. We generated repetitive sequences of length 1007, with repeat length on the x-axis and a 10% repeat mutation substitution rate. We used a k-mer size of 8 and a window size of 19, for an expected random minimizer density of 0.1 over the 1000 k-mers of the sequence. All data points are an average of 400 random runs, with standard error bars. (left) The average Hamming distance of the minimizers from all k-mers in the sequence is basically the same for random minimizers and Gaussian convolutions; this is consistent with Theorem 2. (center) However, the average distance from the other minimizers is significantly lower for Gaussian convolutions, as predicted by Theorem 3. (right) On repetitive windows of a sequence, Gaussian convolutions tend to have lower density than random minimizers.
relying on CNNs to broadly learn interesting features. We envision training hash functions that are weighted towards particular biologically significant k-mers. Recent work in the computational biology literature has demonstrated that it is possible to use deep neural networks to train better minimizer schemes [21], but that work treats minimizers as just another function to be learned. This does highlight the primary limitation of our work, which is that our analyses only hold at initialization time, and more sophisticated mathematical machinery is necessary to understand behavior after training.
Some of the other seeming limitations are related to generalizing our results beyond a single layer with a single convolutional filter and stride lengths of one, but these limitations are actually easily overcome. Our theorems generalize to 2D (or 3D) filters, at only the cost of notational complexity. Longer stride lengths simply amount to a sparsification of the redundancy found in neighboring minimizers; minimizer schemes sparsify through deduplication of the minimums, but that operation is not easily vectorized, so CNNs instead sparsify by using longer stride lengths. Stride-length sparsification is less efficient space-wise than a full deduplication, but with high probability conveys the same information, provided that the strides are not too long (Figure 1).
On the other hand, multiple filters within a layer correspond to just taking multiple minimizers within each region; this corresponds roughly to generating a full MinHash-style sketch of each window (though it does not work for Jaccard similarity because Gaussian convolutions are not min-wise independent), capturing more information than a single minimizer does. Another reason why this may be helpful for CNNs is due to the fact that memorizing all the output values of a single neuron is possible for CNNs, but rather hard in training time; thus, breaking up the minimizer information across multiple filters likely makes it easier to train. Furthermore, having multiple layers of convolutional filters effectively creates minimizer schemes that are able to learn more complicated hash functions than just Gaussian dot products. These theoretical connections deserve further study.

Conclusion
In this manuscript, through a careful probability computation, we proved that the family of hash functions defined by Gaussian dot products is useful for minimizer style analysis. By recasting CNN convolutional filters in a hash-function based framework, we were able to demonstrate their equivalence to minimizers, one of the workhorses of computational biology. Furthermore, we validated our theory empirically, showing a lowered density in repetitive regions for Gaussian convolution minimizers. We hope that the connection proves fruitful for both methods, enabling the design of better minimizers, as well as providing some mathematically rigorous justification for why CNNs work in categorical data space.