For the last decade plus, a standard approximation heuristic for bioinformatics sequence comparison was to use k-mer sketching techniques. These techniques typically estimate similarity using purely sampled k-mer compositional overlap. However, using only presence/absence of k-mer features eschews the linear ordering of k-mers on a genome, which can cause a systematic bias in the presence of large structural differences, which can happen both because of evolution and because of incompleteness in metagenome assemblies. To resolve this issue, in 2023, we introduced skani, a method for quickly determining the ANI (average nucleotide identity) between bacterial genomes, which is 20x faster than the previously state-of-the-art FastANI and more accurate on incomplete and possibly contaminated genomes. The key is to perform chaining on subsampled k-mers and then reuse those chains for ANI estimation. However, another shortcoming of k-mer sketching based methods is that although we can efficiently compare entire genome similarity, resolving local alignments is difficult without an expensive base-level dynamic programming. In unpublished work, we introduce alamem, which efficiently estimates ANI of local alignments using chained MEM (maximal exact matches) length and gap statistics, and alasight, a method for finding novel signatures of horizontal gene transfer (and potential candidate mobile genetic elements) by performing local alignment of bacterial genomes against the entire Genome Taxonomy Database in times on the order of less than a minute.

Zoom Link: https://umd.zoom.us/j/93438848888?pwd=GbAvOYwxCGXfYET93bTDSFfMFgwSuf.1