Spectral Jaccard Similarity

Spectral Jaccard Similarity estimates pairwise similarity between sequencing reads to provide a refined proxy for alignment size in noisy third-generation long-read sequencing data.

Key Features:

• Min-Hash-Based Estimation: Leverages min-hash techniques to approximate the Jaccard similarity between sets of k-mers from sequencing reads via min-hash collisions.
• Spectral Analysis: Constructs a min-hash collision matrix (rows represent read pairs, columns represent hash functions) to correct biases from non-uniform k-mer distributions, including genome-wide GC bias and common k-mers.
• Singular Value Decomposition (SVD): Computes an offset-adjusted SVD of the collision matrix and uses the leading left singular vector as a refined similarity estimate that accounts for uneven k-mer distributions.
• Approximation Method: Provides an approximate computation that uses a single matrix-vector product to avoid a full SVD for improved computational efficiency.
• Filtering with Traditional Jaccard: Applies traditional Jaccard similarity estimates to pre-filter candidate read pairs prior to spectral refinement.

Scientific Applications:

• Genomic read overlap detection: Provides refined proxies for alignment size useful in read overlap detection and assembly pipelines.
• Long-read sequencing analysis: Targets noisy third-generation long-read technologies such as PacBio reads.
• Complex genomes and metagenomics: Addresses k-mer distribution variability relevant to analyses of complex genomes and metagenomic datasets.
• Benchmarking on NCTC PacBio data: Demonstrated improvements in filter Area Under the Curve (AUC) across 40 PacBio datasets from the NCTC collection.

Methodology:

Candidate read pairs are pre-filtered by traditional Jaccard estimates, a min-hash collision matrix (rows = read pairs, columns = hash functions) is constructed and offset-adjusted, and an SVD is performed to extract the leading left singular vector as the refined similarity; an approximate computation using a single matrix-vector product is provided as an alternative to full SVD.