Metadata-Version: 2.5
Name: minimizer-stream
Version: 1.0.0
Summary: Streaming canonical minimizer sketches for FASTA and FASTQ
Author: Bert Mouler
License: MIT License
        
        Copyright (c) 2026 Bert Mouler
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
License-File: LICENSE
Keywords: bioinformatics,fasta,fastq,minimizer,sketching
Classifier: Development Status :: 5 - Production/Stable
Classifier: Environment :: Console
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Bio-Informatics
Classifier: Typing :: Typed
Requires-Python: >=3.11
Provides-Extra: test
Requires-Dist: hypothesis>=6.100; extra == 'test'
Requires-Dist: mutmut>=3.7; extra == 'test'
Requires-Dist: mypy>=1.14; extra == 'test'
Requires-Dist: pytest-cov>=5.0; extra == 'test'
Requires-Dist: pytest>=8.0; extra == 'test'
Requires-Dist: ruff>=0.6; extra == 'test'
Description-Content-Type: text/markdown

# minimizer-stream

[![CI](https://github.com/bmouler/minimizer-stream/actions/workflows/ci.yml/badge.svg)](https://github.com/bmouler/minimizer-stream/actions/workflows/ci.yml)
![Coverage](https://img.shields.io/badge/coverage-100%25-brightgreen)
![Types](https://img.shields.io/badge/types-mypy%20strict-blue)
![Mutation](https://img.shields.io/badge/mutation-98%25%20killed-brightgreen)
![Python](https://img.shields.io/badge/python-3.11%2B-blue)
[![License](https://img.shields.io/badge/license-MIT-blue)](LICENSE)

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

```bash
python -m pip install minimizer-stream
```

For development and verification:

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

## Quickstart

```bash
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:

```python
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

```mermaid
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:

```bash
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:

```bash
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:

```bash
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.

| Behavior-equivalent rationale | Count |
|---|---:|
| ASCII codec alias | 1 |
| Initial `None` versus empty value, compared only to `Minimizer` instances | 2 |
| `typing.cast` is an identity operation at runtime | 1 |

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