DDLCompare

Script: ddlcompare.sh Package: ddl Class: DDLCompare.java

Pairwise genome comparison using DynamicDemiLog (DDL) bucket matching. Creates a DDL sketch for each input, compares them, and reports WKID, ANI, cardinality, containment, completeness, and bucket-level statistics. Can compare two sequences directly, query a genome against a pre-built DDL reference database, run multi-query batch comparisons, perform per-contig analysis, or run collision tests on a DDL file.

Basic Usage

# Direct pairwise comparison
ddlcompare.sh genome1.fa genome2.fa

# Query against pre-built reference
ddlcompare.sh query.fa ref=ddls.tsv records=10

# Query against bundled RefSeq database
ddlcompare.sh query.fa refseq records=10

# Batch multi-query mode
ddlcompare.sh qf=queries.tsv ref=ddls.tsv t=32

# Collision test on a reference file
ddlcompare.sh ref=ddls.tsv collisiontest

Input may be FASTA or FASTQ, compressed or uncompressed. In pairwise mode, DDLCompare sketches both inputs on the fly using DDL bucket hashing and reports similarity metrics directly. In reference mode, the reference database is loaded once and the query is compared against all entries.

Operating Modes

DDLCompare selects its operating mode based on which parameters are provided:

Pairwise mode: Two positional arguments or in= and in2= — compares two sequences directly and reports detailed similarity metrics.
Query mode: in= (or positional first argument) with ref= — sketches the query and compares it against every entry in the pre-built reference database.
Multi-query batch mode: qf= with ref= — loads pre-built query sketches from a TSV file and compares all queries against all references in parallel.
Per-contig mode: in= with ref= and percontig=t — sketches each contig or sequence in the query file independently and reports the best match for each.
Collision test: ref= with collisiontest — measures the all-pairs collision rate in a DDL reference file to evaluate database quality.

Memory and Threading

DDLCompare is configured with a fixed heap of 3200m by default, which is sufficient for most reference databases. When comparing against RefSeq (millions of entries), increase heap with -Xmx as needed. Threading defaults to all available cores. For single-query reference mode, the comparison loop is single-threaded but fast enough for large databases. Multi-query batch mode uses a thread pool to process queries in parallel.

Parameters

Pairwise Input Parameters

in=<file>: First input file (query). Also accepts the first positional argument.
in2=<file>: Second input file (reference). Also accepts the second positional argument. Used only in pairwise mode.
query=<file>: Alias for in=. Explicitly sets the query file for reference or per-contig mode.

Reference Mode Parameters

ref=<file>: Pre-built DDL reference file in TSV format, as produced by DDLWriter or DDLLoader. Activates reference mode when set. Also accepts ref=refseq as a shorthand for the bundled RefSeq database.
refseq: Shorthand for loading the bundled RefSeq DDL sketch database from resources/. Equivalent to ref=refseq. Resolves to the highest-resolution available file: refseqSketchDDL_k25e5b4096.tsv.gz preferred, falling back to 2048-bucket variants.
queryfile=<file>: (qf) Pre-built DDL query file in TSV format. When set alongside ref=, activates multi-query batch mode. All queries are compared against all references. Query names are printed automatically in this mode.
qf=<file>: Alias for queryfile=.
records=20: (maxrecords) Maximum number of top hits to display per query. Only the best-matching references by matching bucket count are reported.
minhits=5: Minimum number of matching DDL buckets required to report a hit. Filters out weak or coincidental matches. Increase to reduce false positives at the cost of sensitivity for distantly related sequences.
index=f: Build and use an inverted index for query acceleration. When enabled, only references with at least minhits bucket overlaps are fully compared, dramatically reducing comparisons for large databases. Useful in multi-query batch mode with many queries.
t=auto: Number of threads. Defaults to all available cores. Used for parallel loading and multi-query comparison.

Per-Contig Parameters

percontig=f: (persequence) When enabled, each contig or sequence in the query file is sketched and compared independently. Useful for metagenomic assemblies where different contigs may originate from different organisms. Query names are printed automatically in this mode.
perfile=t: Opposite of percontig. When set to false (perfile=f), activates per-contig mode. Provided as an alternative flag for clarity.
minsketch=400: (minsketchlen) Minimum sketch size (in bases) to include a contig in per-contig mode. Contigs that produce sketches smaller than this threshold are skipped. Prevents very short contigs from generating noisy comparisons.

Sketch Parameters

k=25: K-mer length for hashing. Must match the k value used to build the reference database. Changing k invalidates comparisons against existing databases. Default of 25 balances specificity and sensitivity for genomic sequences.
buckets=2048: Number of DDL buckets in the sketch. More buckets improve accuracy of similarity estimates at the cost of memory and sketch file size. When querying a pre-built reference, this is auto-set to match the reference database's bucket count.
exponent=6: (ebits) Exponent bits for DDL bucket encoding. Range 1-8. Controls the precision of each bucket's stored value. Default of 6 provides good precision for most use cases. Must match the reference database when querying.

Blacklist Parameters

blacklist=<file>: Explicitly set the blacklist file to use. The blacklist filters taxonomically uninformative k-mers (e.g., highly conserved sequences present across all life) from query sketch construction. Pre-built reference sketches already have blacklisting applied; this parameter affects the query sketch only.

By default, DDLCompare autoloads genomeDDLBlacklist_k25e5b4096.fa.gz from the resources/ directory if present. No explicit parameter is needed for standard usage.

Output Format Parameters

format=tab: Output format. Values: tab (tabular, default), json, oneline (query/ref/ANI three-column). Can also be specified as format=0 (tab), format=1 (json), format=2 (oneline).
json=f: Shorthand for format=json. Outputs results as a JSON array.
noheader=f: Suppress the column header line in tabular output.

Output Column Parameters

The following parameters control which columns appear in output. Default columns are ANI, WKID, Completeness, Matches, Bases, TaxID, and Name.

ani=t: (printani) Print the Average Nucleotide Identity estimate.
wkid=t: (printwkid) Print the Weighted K-mer Identity (raw DDL similarity score).
completeness=t: (printcompleteness) Print the completeness metric — how completely the query covers the reference.
containment=f: (printcontainment) Print the containment metric — fraction of the query contained in the reference.
matches=t: (printmatches) Print the number of matching DDL buckets between query and reference.
bases=t: (printbases) Print the reference genome base count.
taxid=t: (printtaxid, showtaxid, printtid, showtid) Print the NCBI taxonomy ID of the reference entry.
name=t: (printname, showname) Print the reference sequence name.
cardinality=f: (printcardinality, card) Print the estimated cardinality (unique k-mer count) of the reference.
queryname=f: (printqueryname, qname) Print the query sequence name. Enabled automatically in multi-query and per-contig modes.
ssuani=f: (printssu) Print the SSU (16S/18S rRNA) alignment identity when SSU mode is active.
type=f: (printtype) Print the SSU rRNA type (16S or 18S) when SSU mode is active.
qlen=f: (printqlen) Print the query SSU sequence length when SSU mode is active.
rlen=f: (printrlen) Print the reference SSU sequence length when SSU mode is active.
rank=f: (printrank) Print the taxonomic rank of the reference entry.
lineage=f: (printlineage) Print the full taxonomic lineage of the reference entry.
printall=f: Enable all output columns simultaneously. Equivalent to setting every print* parameter to true.
alignani=f: (usealignmentani) When SSU mode is active, use SSU alignment identity instead of DDL-estimated ANI for the ANI column.

SSU / rRNA Parameters

ssu=f: Enable SSU (small subunit rRNA) mode. When enabled, DDLCompare extracts 16S or 18S rRNA sequences from query and reference genomes using a PGM gene caller and performs pairwise alignment to compute SSU identity alongside DDL similarity. Useful for validating taxonomy assignments. Requires SSU reference databases in resources/.
parallelload=t: (pload) Load SSU reference databases in parallel with DDL reference loading when ssu=t. Reduces total startup time in SSU mode. Enabled by default.

Collision Test

collisiontest: Run an all-pairs collision test on the reference file specified by ref=. Measures how often unrelated genomes share DDL bucket values by chance. Reports total pairs tested, total matches, average matches per pair, maximum matches in any pair, and average per-bucket collision rate. Used to evaluate database quality and validate sketch parameters.

Java Parameters

-Xmx: Set Java heap size. Default is 3200m (3.2 GB). Increase for very large reference databases: e.g., -Xmx8g for RefSeq-scale databases.
-eoom: Exit if an out-of-memory exception occurs. Requires Java 8u92+.
-da: Disable assertions.

Examples

Direct Pairwise Comparison

# Compare two genomes directly
ddlcompare.sh ecoli.fa mruber.fa

# Specify sketch parameters explicitly
ddlcompare.sh ref.fa mutant.fa k=25 buckets=2048

Pairwise mode sketches both inputs on the fly and prints a summary including ANI, WKID, completeness, base counts, cardinality, and bucket match statistics. Useful for quick similarity checks between two sequences without a pre-built database.

Query Against RefSeq Database

# Query against the bundled RefSeq DDL database
ddlcompare.sh unknown_genome.fa refseq records=10

# Same with explicit records limit and compressed input
ddlcompare.sh query.fq.gz ref=refseqSketchDDL_k25e5b2048.tsv.gz records=5

The refseq shorthand automatically resolves to the highest-resolution RefSeq DDL sketch file present in the resources/ directory. Results are sorted by matching bucket count and the top records= hits are reported. The bucket count is auto-set to match the reference database.

Multi-Query Batch Mode

# Compare many pre-built query sketches against a reference database
ddlcompare.sh qf=top1k.tsv.gz ref=refseqSketchDDL_k25e5b2048.tsv.gz t=32

# Same with inverted index for faster comparison
ddlcompare.sh qf=queries.tsv ref=ddls.tsv t=32 index=t records=5

Multi-query batch mode loads pre-built sketch files for both queries and references. All queries are compared against all references using a thread pool. The inverted index (index=t) can dramatically reduce the number of comparisons performed when queries match only a small fraction of references. Timing information including index efficiency is printed to stderr.

Per-Contig Mode for Metagenomics

# Classify each contig in a metagenomic assembly individually
ddlcompare.sh assembly.fa ref=refseqSketchDDL_k25e5b2048.tsv.gz percontig=t records=3

# Skip very short contigs
ddlcompare.sh assembly.fa refseq percontig=t minsketch=1000 records=1

Per-contig mode sketches each sequence in the input FASTA independently. Useful for metagenomic assemblies where contigs from different organisms are mixed. The query name column is printed automatically. The minsketch parameter filters out contigs too short to produce reliable sketches.

Custom Output Columns

# Compact three-column output: query, reference, ANI
ddlcompare.sh query.fa refseq format=oneline

# Full JSON output with all fields
ddlcompare.sh query.fa refseq json=t printall=t records=5

# Tabular output with containment and lineage columns added
ddlcompare.sh query.fa ref=custom.tsv containment=t lineage=t records=20

The default tabular output includes ANI, WKID, completeness, matches, bases, taxID, and name. Individual columns can be enabled or disabled by name. The oneline format produces compact three-column output suitable for downstream parsing.

Collision Test

# Test all-pairs collision rate in a custom reference database
ddlcompare.sh ref=custom_db.tsv collisiontest

The collision test computes pairwise bucket overlap for every pair of entries in the reference database. It reports total pairs tested, total bucket matches, average matches per pair, the maximum matches seen in any single pair, and the per-bucket average collision rate. Low collision rates (well below 1 match per pair on average) indicate a high-quality, low-redundancy database.

Algorithm Details

DynamicDemiLog (DDL) Sketching

DDLCompare uses the DynamicDemiLog algorithm to create compact sketches of genomic sequences. Each sketch consists of a fixed number of buckets; each bucket stores the minimum hash value seen among all k-mers whose hash maps to that bucket. This is analogous to MinHash but with partitioned buckets rather than a global minimum heap.

Similarity between two DDL sketches is measured by counting matching buckets — buckets where both sketches have stored the same minimum hash value. The matching bucket count drives all reported metrics:

WKID: Weighted K-mer Identity — raw ratio of matching buckets to total buckets.
ANI: Average Nucleotide Identity — derived from WKID through a mathematical transformation accounting for k-mer length.
Completeness: How completely the query covers the reference, normalized by the expected number of matches for a genome of that size.
Containment: Fraction of the query's k-mer space found in the reference.
Cardinality: Estimated number of unique k-mers in the genome, derived from bucket fill statistics.

Blacklisting

Highly conserved genomic regions (e.g., ribosomal RNA genes, universal housekeeping genes) produce k-mers that appear across virtually all organisms and carry no taxonomic information. When a blacklist file is present in resources/, DDLCompare filters these k-mers from query sketch construction. Pre-built reference databases already have blacklisting applied at build time, so the blacklist only needs to be applied to the query side.

Inverted Index

In multi-query or large-reference scenarios, brute-force pairwise comparison of every query against every reference is expensive. The inverted index maps each bucket value to the list of reference entries containing it. When a query arrives, the index quickly identifies which references share at least minhits bucket values with the query; only those candidates are fully compared. This can reduce actual comparisons by orders of magnitude when queries match only a small fraction of the database.

Auto-Bucket Matching

When loading a pre-built reference database, DDLCompare reads the bucket count from the first record and automatically adjusts the query bucket count to match, regardless of what buckets= was set to on the command line. This ensures that queries are always compared against references using the same sketch resolution.

Related Tools

DDLCompare is part of the DDL toolkit for genomic comparison:

DDLWriter (ddlwriter.sh): Build DDL sketch databases from collections of genome sequences. Produces the TSV files used as ref= input for DDLCompare.
DDLBlacklist (ddlblacklist.sh): Generate blacklist files from a set of reference genomes to identify and filter taxonomically uninformative k-mers.
DDLMerger (ddlmerger.sh): Merge multiple DDL sketch databases into a single file, or merge per-sequence sketches into per-genome sketches.
QuickClade (quickclade.sh): Higher-level taxonomic classification tool that uses DDL comparison under the hood to classify sequences against a curated database with full lineage output.

Support

For questions and support:

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