minimizer-stream

A dependency-free Python library and command-line program that streams canonical minimizer sketches from FASTA and four-line FASTQ. Output includes record, zero-based position, stable 64-bit FNV-1a hash, canonical strand, and canonical k-mer.

Install

python -m pip install minimizer-stream

For development and verification:

python -m pip install -e '.[test]'
ruff check .
pytest --cov=minimizer_stream --cov-branch --cov-fail-under=100

Quickstart

minimizer-stream reads.fasta -k 21 -w 10 > sketch.tsv
minimizer-stream reads.fastq -k 21 -w 10 --format jsonl --deduplicate
cat reads.fasta | minimizer-stream - -k 15 -w 5

TSV has no header and its columns are record, position, hash, strand, kmer. JSONL uses the same field names. The Python API is lazy:

from minimizer_stream import minimizers, naive_minimizers

for item in minimizers("ACGTTGCA", k=3, w=2, deduplicate=True):
    print(item.position, item.hash, item.strand, item.kmer)

assert list(minimizers("ACGTTGCA", 3, 2)) == list(naive_minimizers("ACGTTGCA", 3, 2))

Algorithm

flowchart LR; R[FASTA/FASTQ] --> K[canonical k-mers]; K --> H[FNV-1a 64-bit]; H --> D[monotonic deque, window w]; D --> M[leftmost minimum]; M --> U{deduplicate?}; U --> O[record, position, hash, strand, kmer]

Each k-mer is compared lexicographically with its reverse complement; the smaller representation is canonical, with palindromes assigned to the forward strand. Canonical strings are hashed with deterministic 64-bit FNV-1a, never Python's process-randomized hash. A monotonic deque retains possible minima for each window, removing expired entries from the front and strictly larger hashes from the back. Keeping equal hashes preserves deterministic leftmost tie-breaking.

Constructing, reverse-complementing, and hashing each canonical k-mer costs $O(k)$ in this pure-Python implementation. The monotonic-deque path is therefore $O(nk)$ total with $O(w+k)$ working memory, versus $O(n(k+w))$ for naive_minimizers, which additionally scans each minimizer window. Non-ACGT characters reset both k-mer construction and the minimizer window, so no output spans an invalid base.

Reproducible capability evidence

The deterministic benchmark seeds its input and first requires both implementations to produce exactly identical objects:

python benchmarks/benchmark.py --length 50000 --k 21 --w 50 --repeats 3

On an Apple M3 Max with Python 3.11.12, that command produced 49,931 identical selections and median times of 0.130359 seconds for the deque implementation and 0.195500 seconds for the oracle, a 1.50x speedup. Timing depends on hardware and Python version; the durable claim is removing the extra $O(nw)$ window scan through amortized $O(n)$ deque maintenance, while shared k-mer construction remains $O(nk)$. The exhaustive deterministic randomized test also compares both APIs across lengths 0–39 and all combinations of k and w from 1–5.

Verification

CI runs Ruff, strict mypy, and the full property-based and deterministic test suites on Linux and macOS with Python 3.11–3.13. Its exact coverage command is:

pytest --cov=minimizer_stream --cov-branch --cov-fail-under=100

Tests include reverse complements, palindromes, ties, invalid-base resets, short and lowercase sequences, FASTA, FASTQ, malformed records, invalid parameters, subprocess execution from a clean temporary directory, TSV, JSONL, standard input, and deduplication.

Mutation testing

From the repository root, reproduce the mutation run with:

source .venv/bin/activate
mutmut run
mutmut results

Mutation testing generated 392 mutants and killed 388 (98.98%). The remaining 4 survivors were reviewed as behavior-equivalent, not missed mutants; the run had zero suspicious mutants and zero timeouts.

Limitations

• FASTQ must use the conventional four-line form; wrapped sequence or quality lines are rejected.
• FASTA permits wrapped sequence lines but rejects blank lines and empty records.
• Record names containing control characters or beginning with =, +, -, or @ are rejected so default TSV output keeps five columns and is safe from spreadsheet formula interpretation.
• Input is decoded as ASCII; compressed files must be decompressed before use.
• Record sequences are retained one at a time. The parser does not load the full file, but an individual record must fit in memory.
• w counts consecutive valid k-mers, not bases. A valid window therefore spans k + w - 1 bases.
• Hash collisions are possible for any 64-bit sketch; the canonical k-mer is emitted so callers can distinguish them when needed.