Spectral Jaccard Similarity for long-read alignment

A key step in genomic analysis pipelines is the identification of regions of similarity between pairs of DNA sequencing reads. This task, known as pairwise sequence alignment, is a heavy computational burden, particularly in the context of third-generation long-read sequencing technologies, which produce noisy reads. A common approach to address this issue is to view the Jaccard similarity between the set of k-mers of each read as a proxy for the alignment size. A full dynamic-programming-based alignment is then performed only on pairs of reads with high Jaccard similarity. This strategy has the added benefit that the Jaccard similarities don't need to be computed exactly, and can instead be efficiently estimated through the use of min-hashes. This is done by hashing all k-mers on a read and computing the minimum hash value (the min-hash) for each read. For a randomly chosen hash function, the collision probability for the min-hashes of two distinct reads is precisely their Jaccard similarity. Hence, one can estimate the Jaccard similarity by computing the fraction of min-hash collisions out of the set of hash functions considered. However, when the k-mer distribution of the reads being considered is significantly non-uniform, the Jaccard similarity is no longer a good proxy for the alignment size. In particular, genome-wide GC biases and the presence of common k-mers increase the probability of a min-hash collision, thus biasing the estimate of alignment size provided by the Jaccard similarity. In this work, we introduce a min-hash-based approach for estimating alignment sizes called Spectral Jaccard Similarity, which naturally accounts for an uneven k-mer distribution in the reads being compared. The Spectral Jaccard Similarity is computed by considering a min-hash collision matrix (where rows correspond to pairs of reads and columns correspond to different hash functions), centering it, and performing a singular value decomposition. The leading left singular vector provides the Spectral Jaccard Similarity for each pair of reads, while the corresponding right singular vector can be understood as a measure of the unreliability of each hash function. Intuitively, a hash function that assigns low values to common k-mers is more unreliable for estimating alignment size, since it is more likely to create spurious min-hash collisions. Implicitly, this approach leads  to a kind of weighted Jaccard similarity, where the weight of different hash functions is learned from the dataset. Experiments on PacBio long-read sequencing data from several bacterial genomes, spanning a variety of k-mer distributions, show that the Spectral Jaccard Similarity is significantly more correlated with alignment size than the standard Jaccard Similarity. When used as a metric to filter out pairs of reads that are unlikely to have a large alignment, Spectral Jaccard Similarity outperforms Jaccard Similarity on standard classification performance metrics. As an example, when applied to filtering pairs of reads which have an overlap of at least 30%, the area under the ROC curve (AUC) obtained by Spectral Jaccard Similarity filtering varied between 0.92 and 0.95 on five test datasets, while the AUC obtained by Jaccard Similarity filtering varied between 0.76 and 0.88.