kssd

kssd performs sketching-based resemblance and containment analyses of omics sequences by sampling k-mer substring space to enable efficient large-scale sequence comparison.

Key Features:

• Accurate Sequence Sketching: kssd employs k-mer substring space sampling instead of local-sensitive hashing methods to sketch sequences, improving accuracy for resemblance estimation across datasets including sequences of disparate sizes.
• Efficiency in Containment Analysis: In containment analysis, kssd reports higher accuracy than mash screen while using 110,535-fold less storage and 2,623-fold less CPU time.
• Robustness Across Sequence Sizes: Maintains accurate estimates irrespective of large size disparities between compared sequences.
• Wide Compatibility with Data Formats: Supports FASTA and FASTQ formats, including gzipped files.
• Statistical Foundations: The underlying algorithm is accompanied by proofs of statistical properties that explain its performance characteristics.

Scientific Applications:

• Resemblance Analysis: Estimating sequence resemblance to detect genetic similarities and infer evolutionary relationships.
• Containment Analysis: Testing sequence containment to detect gene presence and characterize genomic architecture.

Methodology:

Decompose sequences into k-mer substrings, sample the k-mer substring space to construct compact sketches, and compare sketches for resemblance and containment without processing complete datasets.