Low-complexity kmer filter

Low-complexity kmers (homopolymer runs, tandem repeats) can dominate an index without carrying useful information. obikmer detects and excludes them during index construction using a normalized Shannon entropy score.

Sub-word frequencies

For a kmer of length k and a sub-word size ws (1 \le ws \le ws_{\max}, default ws_{\max} = 6), the kmer is decomposed into its k - ws + 1 overlapping sub-words of length ws by sliding a window across it. Each sub-word is tallied under its raw 2-bit-packed value, with no canonicalization.

Corrected Shannon entropy

Let f_j be the observed count of raw sub-word j, and n_{\text{words}} = k - ws + 1 the total number of sub-words. The entropy is:

H_{\text{corr}} = \log(n_{\text{words}}) - \frac{1}{n_{\text{words}}} \sum_j f_j \log f_j

Small-sample correction

Because only n_{\text{words}} sub-words are observed among up to 4^{ws} possible values, the achievable maximum entropy H_{\max} is bounded below \log(4^{ws}) for small samples. H_{\max} is computed from the most uniform integer distribution achievable with n_{\text{words}} observations over 4^{ws} categories. The normalized entropy is:

\hat{H}(ws) = \frac{H_{\text{corr}}}{H_{\max}} \in [0, 1]

A value near 0 indicates low complexity (e.g. a homopolymer run); near 1 indicates high complexity, characteristic of a random sequence.

Final score

The filter evaluates \hat{H}(ws) for every word size from 1 to ws_max and keeps the minimum:

\text{entropy}(kmer) = \min_{ws=1}^{ws_{\max}} \hat{H}(ws)

Taking the minimum across word sizes ensures that repetition at any scale is detected: a homopolymer is caught at ws=1, a dinucleotide repeat at ws=2, and so on. A kmer is rejected if its entropy score falls below a threshold \theta (default 0.7), a configurable collection parameter.

Properties

The entropy score depends only on the kmer sequence itself, not on where or how many times it occurs:

Orientation invariance: a kmer and its reverse complement always receive the same score.
Context independence: a given kmer is always accepted or always rejected, regardless of which genome or read it appears in. The filter defines a fixed partition of the kmer space into low-complexity and valid kmers.

Low-complexity kmer filter

Sub-word frequencies

Corrected Shannon entropy

Small-sample correction

Final score

Properties

Wiki sidebar

Theory

Kmer indexing

Phylogeny

Kmer-based

SNP-based

Usage

Formats