kmer-diff

A k-mer based tool for detecting duplications and differences between closely related bacterial genome sequences.

Overview

kmer-diff compares FASTQ files from bacterial isolates to identify:

• Differentially abundant regions: Genomic segments present at different copy numbers between samples (duplications, deletions)
• Unique regions: Sequences present in one sample but absent in another (gene gain/loss, phage, plasmids)
• SNP signatures: Single nucleotide differences detected via k-mer presence/absence patterns

The tool is designed for comparing very closely related strains (last common ancestor within a few years) where differences are sparse but biologically significant.

Approach

Rather than performing full genome assembly, kmer-diff works directly with k-mer counts from raw reads:

1. Build a k-mer count database from paired-end FASTQ files
2. Normalize counts to copy number using estimated chromosomal coverage
3. Compare samples to identify k-mers with significant copy number differences
4. Merge adjacent differential k-mers into contiguous regions
5. Locate regions on a reference genome (optional)

Installation

Requires Python 3.10+. Installing into a virtual environment is recommended so the kmer-diff command and its dependencies stay isolated from your system Python.

# Clone the repository
git clone https://github.com/yourorg/kmer-diff.git
cd kmer-diff

# Create and activate a virtual environment
python3 -m venv .venv
source .venv/bin/activate        # Windows: .venv\Scripts\activate

# Install the package (add [dev] for test/lint/type-check tools)
pip install -e ".[dev]"

# Verify the CLI is available
kmer-diff --help

Activate the virtual environment (source .venv/bin/activate) in each new shell before running kmer-diff. Alternatively, call the executable directly without activating: .venv/bin/kmer-diff --help.

Note: A virtual environment is tied to its absolute path. If you move or rename the project directory, recreate it: rm -rf .venv && python3 -m venv .venv && pip install -e ".[dev]".

Quick Start

# Build k-mer databases from local FASTQ files
kmer-diff build --r1 sample_a_R1.fastq.gz --r2 sample_a_R2.fastq.gz -o sample_a.kdb
kmer-diff build --r1 sample_b_R1.fastq.gz --r2 sample_b_R2.fastq.gz -o sample_b.kdb

# Or build directly from an SRA accession (downloads from ENA automatically)
kmer-diff build --sra SRR12345678 -o sample.kdb

# Compare two samples
kmer-diff compare sample_a.kdb sample_b.kdb -o results/

# Compare all samples and generate distance matrix
kmer-diff compare-all sample_a.kdb sample_b.kdb sample_c.kdb -o results/

Commands

build

Convert paired-end FASTQ files to a k-mer count database.

# From local files
kmer-diff build --r1 <R1.fastq.gz> --r2 <R2.fastq.gz> -o <output.kdb> [options]

# From SRA accession
kmer-diff build --sra <accession> -o <output.kdb> [options]

Options:

• --r1/--r2: Local paired-end FASTQ files (gzipped or uncompressed)
• --sra: SRA accession (SRR/ERR/DRR) to download from ENA. Mutually exclusive with --r1/--r2
• --kmer-size: K-mer length (default: 31)
• --min-count: Minimum count threshold to filter sequencing errors (default: 3)

compare

Compare two samples and identify differential regions.

kmer-diff compare <a.kdb> <b.kdb> -o <output_dir> [options]

Options:

• --threshold: Copy number difference threshold (default: 0.7)
• --core-genes: FASTA file of single-copy core genes for improved normalization
• --reference: Reference genome FASTA for mapping regions to coordinates

compare-all

Compare multiple samples pairwise and generate a distance matrix.

kmer-diff compare-all <sample1.kdb> <sample2.kdb> ... -o <output_dir> [options]

Options:

• --threshold: Copy number difference threshold (default: 0.7)
• --core-genes: FASTA file of single-copy core genes for improved normalization
• --reference: Reference genome FASTA for mapping regions to coordinates
• --full-pairwise: Generate detailed reports for each pair (default: matrix only)

Output Files

Pairwise comparison (compare)

output_dir/
  summary.tsv              # Overall statistics
  differential_regions.tsv # Regions with copy number differences
  unique_to_a.tsv          # Regions present only in sample A
  unique_to_b.tsv          # Regions present only in sample B
  branching_flags.tsv      # Complex regions requiring manual inspection
  differential_regions.bed # Coordinates (if --reference provided)
  unique_to_a.bed          # Coordinates (if --reference provided)
  unique_to_b.bed          # Coordinates (if --reference provided)

All-vs-all comparison (compare-all)

output_dir/
  distance_matrix.tsv      # NxN pairwise distance matrix
  pairwise/                # Per-pair details (if --full-pairwise)
    a_vs_b/
    a_vs_c/
    ...

Distance Metric

The distance between two samples is calculated as:

Total bases in differential regions per megabase of shared genome

This normalized metric accounts for variable sequencing quality and shared genome size, making distances comparable across sample pairs.

Algorithm Details

See IMPLEMENTATION.md for detailed algorithm descriptions.

Testing

# Generate synthetic test data
python generate_test_data.py -o test_data/

# Run tests
pytest tests/

License

MIT License