Spectral Jaccard Similarity: A New Approach to Estimating Pairwise Sequence Alignments

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Pairwise sequence alignment is a computational bottleneck in genomic analysis, especially with third-generation sequencing.
• Min-hashes estimate k-mer Jaccard similarity to filter reads, but accuracy decreases with non-uniform k-mer distributions (e.g., GC biases, repeats).

Purpose of the Study:

• Introduce Spectral Jaccard Similarity, a min-hash-based method to estimate alignment sizes.
• Address limitations of standard Jaccard similarity in handling uneven k-mer distributions.
• Provide a computationally efficient estimator for spectral similarity scores.

Main Methods:

• Developed a min-hash-based approach for estimating alignment sizes.
• Computed Spectral Jaccard Similarity via singular value decomposition of a min-hash collision matrix.
• Designed a computationally efficient estimator for spectral similarity scores.

Main Results:

• Spectral Jaccard Similarity accounts for uneven k-mer distributions.
• Empirically demonstrated significantly improved estimates for alignment sizes compared to traditional methods.
• Validated the computational efficiency of the new estimator.

Conclusions:

• Spectral Jaccard Similarity offers a more accurate metric for read pair filtering in genomic analyses.
• This method enhances the efficiency and reliability of bioinformatics pipelines dealing with complex sequence data.
• The approach is particularly valuable for third-generation sequencing data characterized by non-uniform k-mer frequencies.