Sketch

Overview

Sketch creates compact hash-based representations of sequences using the MinHash algorithm. These sketches can be used for:

• Taxonomic identification - Identify species from assemblies or raw reads
• Reference database creation - Build searchable sketch databases from RefSeq, nt, or custom sequences
• Contamination detection - Screen for contaminating organisms in sequencing data
• Rapid similarity screening - Compare sequences without expensive alignments

Sketch is typically used as part of a larger workflow where sketches are created once and queried many times using CompareSketch or SendSketch.

Quick Start

sketch.sh in=genome.fasta out=genome.sketch

sketch.sh in=refseq.fa.gz out=refseq#.sketch files=31 mode=sequence

sketch.sh in=refseq.fa.gz out=refseq#.sketch files=31 mode=taxa \
  tree=tree.taxtree.gz gi=gitable.int1d.gz taxlevel=subspecies

Parameters

Workflow Examples

# Download and process taxonomy files (see fetchTaxonomy.sh)
# Download RefSeq sequences

# Create taxonomic sketches
sketch.sh in=refseq.fa.gz out=refseq_taxa#.sketch files=31 \
  mode=taxa tree=tree.taxtree.gz gi=gitable.int1d.gz \
  taxlevel=subspecies blacklist=blacklist_refseq_species_1000.sketch

# Start a sketch server for querying
taxserver.sh port=1234 tree.taxtree.gz gi=gitable.int1d.gz refseq_taxa*.sketch

# For Illumina reads
sendsketch.sh in=reads.fq reads=1m samplerate=0.5 minkeycount=2

# For PacBio/Nanopore reads
sendsketch.sh in=long_reads.fq reads=100k size=200k

sketch.sh in=genomes.fasta out=dual_kmer.sketch k=31,24

sketch.sh in=proteins.fasta out=proteins.sketch amino=t k=10

Algorithm Details

MinHash Theory

MinHash sketching creates compact sequence representations through a three-step process:

1. Kmer generation: Extract all length-k kmers from the input sequence
2. Hash calculation: Apply a hash function to convert each kmer to a numerical value
3. Minimum selection: Keep only the N smallest hash values as the "sketch"

For two sequences with sketches of size N and M, comparison requires only O(min(N,M)) operations rather than the O(sequence_length²) required for alignment. Since sketch size is typically fixed (e.g., 10,000 kmers), comparisons run in effectively O(1) time regardless of genome size.

Sketch Size Strategies

The SketchMaker class implements three sizing approaches:

• Fixed size (size parameter): All sketches contain exactly the same number of kmers
• Autosize (default): Sketch size scales nonlinearly with genome complexity. A bacterial genome (~4Mbp) gets ~10,000 kmers, while a human genome gets ~60,000 kmers (only 6x larger despite being 800x larger)
• Density-based (density parameter): Fixed fraction of all genomic kmers. A 4.5Mbp bacterium with density=0.001 gets a 4,500-kmer sketch

Taxonomic Processing

In taxa mode, sequences are grouped by taxonomic classification using:

• Header parsing: Extracts taxonomic information from sequence headers (NCBI or Silva format)
• ID resolution: Maps GI numbers or accessions to NCBI taxonomy using lookup tables
• Level promotion: Groups sequences at the specified taxonomic level (e.g., subspecies, species)
• Quality filtering: Removes uninformative sequences (tossjunk parameter)

Blacklists and Contamination Control

Blacklists filter out uninformative kmers that occur in many unrelated organisms:

• Low-complexity kmers: Poly-A runs, simple repeats
• Highly conserved regions: Universal primer sites, ribosomal conserved regions
• Contamination patterns: Common laboratory contaminants

Built-in blacklists are optimized for major databases (nt, RefSeq, Silva) and automatically loaded when using SendSketch with remote servers.

Depth Tracking

With depth=t, sketches store kmer occurrence counts along with hash values. This enables:

• Coverage estimation: Estimate sequencing depth from kmer frequencies
• Copy number detection: Identify repetitive elements and their copy numbers
• Contamination quantification: Assess relative abundance of different organisms

Depth calculations assume random read distribution and single-copy genomes.

Performance and Scalability

Memory Usage

Memory requirements scale with:

• Sketch size: Larger sketches require more memory but provide higher resolution
• Number of taxa: Taxa mode maintains one sketch per taxonomic unit in memory
• Thread count: Each thread maintains local sketches, automatically capped at 14 threads

I/O Optimization

The implementation optimizes for large datasets through:

• File distribution: Multiple output files enable parallel loading and processing
• Delta compression: Stores hash differences rather than absolute values
• Streaming processing: Processes sequences without loading entire files into memory
• Prefiltering: Automatically enabled for large taxonomic datasets to reduce memory usage

Recommended Usage Patterns

• Assemblies: Use default parameters - assemblies provide the highest quality sketches
• Illumina reads: Use reads=1m, samplerate=0.5, minkeycount=2 to handle errors
• Long reads: Use higher coverage (reads=100k) and larger sketch size (size=200k)
• Large databases: Enable prefilter and use multiple output files for parallel processing

Integration with Other Tools

Sketch is designed as part of the BBSketch ecosystem:

• CompareSketch: Compare query sketches against sketch databases
• SendSketch: Query remote sketch servers (JGI provides public nt, RefSeq, and Silva servers)
• TaxServer: Host sketch databases as HTTP services for rapid querying
• SketchBlacklist: Create custom blacklists from large sequence collections

Support

For detailed information, please read bbmap/docs/guides/BBSketchGuide.txt.

For questions and support:

• Email: bbushnell@lbl.gov
• Documentation: bbmap.org
• Public servers available at JGI for nt, RefSeq, and Silva databases