DDLBlacklist

Basic Usage

ddlblacklist.sh in=sketches.tsv out=blacklist.fa [mincount=20] [k=19]

Input sketch files must have been built with kmers=t in ddlwriter.sh. Multiple input files may be specified as a comma-delimited list; files are processed sequentially and sketch data is discarded after kmer extraction to minimize memory usage.

Two Operating Modes

DDLBlacklist operates in one of two modes:

• Blacklist generation mode (default): Reads sketches, counts genus-level taxa per kmer, writes overrepresented kmers as FASTA. This is the primary mode for building new blacklists.
• Condense mode (condense=t): Condenses double-sized sketches (e.g., 4096 buckets) to half size (2048 buckets) while preferring non-blacklisted kmers. Used with validate=t to measure blacklist effectiveness without re-reading terabytes of raw genome data.

Sketch Requirements

Input sketches must have been built with kmers=t in ddlwriter.sh to store the raw kmer values alongside sketch scores. Sketches built without kmers=t cannot be used for blacklist generation (DDLBlacklist will print an error). The k and exponent parameters must match those used during sketch construction.

Output Header Format

Each blacklisted kmer is written as a FASTA entry. The header encodes taxonomic breadth and sequence complexity:

>kmer_7f3a9c1e2b raw=312 g=312 f=89 o=34 c=15 p=7 k=3 sk=2 e=0.847

raw

Distinct genus-level TaxIDs containing this kmer. This is the primary count used for filtering.

g / f / o / c / p / k / sk

Distinct taxa at genus / family / order / class / phylum / kingdom / superkingdom level, promoted from the genus TaxIDs. These allow post-hoc filtering at any taxonomic resolution using simple awk commands on the FASTA headers.

e

Shannon entropy of the kmer's trimer distribution (0 to 1). Low-entropy kmers are repetitive or low-complexity sequences (e.g., homopolymers or simple repeats). Entropy is calculated using sub-kmers of length entropyk.

The FASTA sequence line contains the decoded kmer nucleotide sequence.

Parameters

Examples

# Step 1: Build double-sized sketches with kmer storage from 16S database
ddlwriter.sh in=16S.fa.gz out=16S_sketches.tsv k=19 buckets=256 exponent=4 \
    mode=pertid kmers=t lineage=t

# Step 2: Generate blacklist at family level
ddlblacklist.sh in=16S_sketches.tsv out=bl_16S_family.fa k=19 exponent=4 \
    mincount=160 validate=t samples=200000

# Step 3: Inspect output headers to verify counts
grep "^>" bl_16S_family.fa | head -5

# Step 1: Build double-sized sketches per clade (run separately for each)
ddlwriter.sh in=refseq.bacteria.fna.gz out=bacteria.tsv.gz k=31 buckets=4096 \
    exponent=5 mode=pertid kmers=t lineage=t tossjunk t=32
ddlwriter.sh in=refseq.archaea.fna.gz out=archaea.tsv.gz k=31 buckets=4096 \
    exponent=5 mode=pertid kmers=t lineage=t tossjunk t=32

# Step 2: Generate combined kmer dump across all clades
ddlblacklist.sh in=archaea.tsv.gz,bacteria.tsv.gz,fungi.tsv.gz,viral.tsv.gz \
    out=combined_dump.fa.gz k=31 exponent=5 mincount=5

# Step 3: Filter combined dump at chosen thresholds using awk
# (genus/250, family/50, order/20, class/10, phylum/5)
zcat combined_dump.fa.gz | awk '/^>/{keep=0; \
    if ($2~/g=/ && ...) keep=1} keep{print}' > filtered_blacklist.fa

# Condense double-sized sketches to normal size while preferring non-blacklisted kmers,
# then validate shared-key statistics across taxonomic distances
ddlblacklist.sh in=archaea.tsv.gz,bacteria.tsv.gz,viral.tsv.gz \
    condense=t validate=t blacklist=genomeDDLBlacklist.fa \
    k=31 exponent=5 samples=200000

Algorithm Details

Genus Promotion

Each sketch record carries a TaxID. Before counting, DDLBlacklist walks the NCBI taxonomy tree upward from the record's TaxID to find the enclosing genus node. All kmers from that record are credited to the genus TaxID, not the original species or strain TaxID. This ensures that a genus with hundreds of sequenced strains does not artificially inflate kmer counts relative to a poorly-sequenced genus.

Multi-Level Header Generation

After collecting the genus-to-kmer mapping, the tool promotes each genus set further up the tree (family, order, class, phylum, kingdom, superkingdom) using distinct-count tracking. The resulting header fields allow post-hoc filtering at any taxonomic level using simple awk commands on the output FASTA, without re-running the tool.

Entropy Filtering

Shannon entropy of the kmer's sub-kmer distribution is computed and written to each header. Entropy is calculated using overlapping sub-kmers of length entropyk (default 3, i.e., trimers) within the full k-mer sequence. The resulting value is normalized to [0, 1] where 0 means perfectly repetitive and 1 means maximally uniform. Setting minentropy > 0 captures low-complexity kmers that should be blacklisted regardless of their taxonomic breadth.

Condense Mode Details

Double-sized sketches have 2N buckets where a normal sketch has N. Condense mode pairs up bucket i with bucket i+N and selects the winner for the condensed bucket. The selection logic is:

• If only one of the pair's kmers is blacklisted, select the non-blacklisted kmer's score.
• If neither or both kmers are blacklisted, select the higher score (standard behavior).

This approximates what would happen if the blacklist were active during original sketching: blacklisted kmers would not compete for bucket slots, and the next-best kmer at each bucket would be used instead.

Validation Statistics

The validate mode samples random pairs of records and computes shared key counts, WKID (Weighted Kmer Identity), and estimated ANI (Average Nucleotide Identity) for each pair, then bins results by the level of the pair's common ancestor in the taxonomy tree. The noise floor metric (average shared keys at class+ distance) is the primary quality indicator: a well-tuned blacklist reduces this substantially while keeping within-genus shared keys near their original value.

Known Blacklist Performance (from shell script documentation)

• Ribosomal blacklist (riboDDLBlacklist.fa.gz): 4,230 unique kmers combining 16S, 18S, and ITS sources. Noise reduction 10–29×; speed improvement 2.6× on all-to-all comparisons.
• Whole-genome blacklist (genomeDDLBlacklist.fa.gz): 23,020 kmers, 571KB. Noise floor reduced from 4.66 to 0.71 average shared keys at class+ distance (6.6×). Genus signal preserved at 99% (145.4 → 143.7 avg shared keys).

Workflow Integration

DDL Tool Suite

DDLBlacklist fits into the DDL (Deterministic Locality-sensitive hashing for Lineage) workflow:

• ddlwriter.sh: Builds DDL sketches from FASTA genome files. Use kmers=t buckets=2×normal to produce the double-sized sketches required as input for DDLBlacklist. Accepts blacklist= to apply an existing blacklist during sketching.
• ddlblacklist.sh (this tool): Analyzes double-sized sketches to identify overrepresented kmers and outputs them as a blacklist FASTA.
• ddlcompare.sh: Computes pairwise distances between DDL sketches for taxonomic classification. Autoloads the genome blacklist by default.
• ddlmerger.sh: Merges multiple blacklist FASTA files with deduplication. Use after generating per-level blacklists to combine them into a single file.
• quickclade.sh: End-to-end taxonomic classification pipeline that uses DDL sketches and blacklists internally.

Blacklist Generation Workflow Summary

1. Build double-sized sketches with kmers=t using ddlwriter.sh.
2. Run ddlblacklist.sh with a low mincount to produce a comprehensive kmer dump.
3. Filter the dump at chosen per-level thresholds using awk on FASTA headers.
4. Merge filtered blacklists using ddlmerger.sh.
5. Validate effectiveness using condense mode (condense=t validate=t).
6. Optionally iterate: re-sketch with the blacklist active to expose second-tier masked kmers, then re-run ddlblacklist.sh on the new sketches and merge.

Applying a Blacklist

Once generated, a blacklist FASTA is applied in two ways:

• During sketching: Pass blacklist=bl.fa to ddlwriter.sh so that blacklisted kmers cannot win bucket slots. This produces cleaner sketches from the start.
• During comparison: DDLCompare autoloads the genome blacklist and ignores blacklisted kmers when computing distances. No additional flags required for the standard genome blacklist.

Support

For questions and support:

• Email: bbushnell@lbl.gov
• Documentation: bbmap.org