The “seeding” step typically involves identifying pairs of reads that share many k-mers (length- k contiguous substrings).

Hence, most practical read aligners follow a “seed-and-extend” paradigm. Furthermore, as shown in Figure 4A, in a typical dataset more than 99.99 % of pairs of reads do not have a significant overlap. One key observation that helps alleviate this computational burden is that in practice one only cares about alignment between reads when there is a significant overlap. However, our ideas can be adapted to the read-to-reference alignment paradigm. For most of this work we discuss alignment in the context of pairwise read alignment. Even for bacterial genome datasets where the number of reads obtained is on the order of n ∼ 10 5, with L ∼ 10 4, this is impractical. For n reads each of length L, the time complexity of aligning all pairs of reads would be O ( n 2 L 2 ). Similarly, the first step in most de novo assembly pipelines 7, 8, 9, 10, 11, 12 is the pairwise alignment of all reads, which is computationally very costly. For n reads each of length L and a reference of length G, the time complexity of aligning all reads to the reference via dynamic programming is O ( n L G ), which is impractical in settings where there are n ∼ 10 5 reads, each of length L ∼ 10 4, with G on the order of 10 6– 10 11 depending on the organism. In reference-based assembly pipelines, 5, 6 where one has a reference of a related organism, the first step usually consists of aligning all reads to the reference i.e., read-to-reference alignment. In both settings naive dynamic-programming-based alignment 2, 3, 4 is impractical due to its quadratic time complexity. Alignment is an integral part of most pipelines in either approach, and is often the most time-consuming step ( Figure S11). Genome assembly is usually performed based on one of two main approaches: de novo assembly, whereby one attempts to assemble a new genome “from scratch” using only the reads obtained, and reference-based assembly, whereby one assembles the reads using a pre-assembled genome of a related organism. 1 While the long reads make resolving repeated sequences easier, the higher error rates make the computational tasks required for assembly significantly more challenging. Unlike short-read technologies, which provide reads of length 100–200 bp with an error rate of 1 %, chiefly substitution errors, long-read technologies provide reads of lengths in the tens of thousands with a nominal error rate of 13%– 15 %, consisting mostly of insertions and deletions. The advent of long-read sequencers such as PacBio and Oxford Nanopore has made the goal of obtaining gold-standard genome assemblies a reality. We empirically show that this new metric provides significantly better estimates for alignment sizes, and we provide a computationally efficient estimator for these spectral similarity scores. The Spectral Jaccard Similarity is computed by performing a singular value decomposition on a min-hash collision matrix. In this work, we introduce a min-hash-based approach for estimating alignment sizes called Spectral Jaccard Similarity, which naturally accounts for uneven k-mer distributions. However, when the k-mer distribution of a dataset is significantly non-uniform (e.g., due to GC biases and repeats), Jaccard similarity is no longer a good proxy for alignment size. To speed up this process, the pairwise k-mer Jaccard similarity is sometimes used as a proxy for alignment size in order to filter pairs of reads, and min-hashes are employed to efficiently estimate these similarities. Pairwise sequence alignment is often a computational bottleneck in genomic analysis pipelines, particularly in the context of third-generation sequencing technologies.