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.