Approximate local alignment via chained MEM divergence estimation for detecting horizontal gene transfer

Abstract

Local alignment tools struggle at querying against thousands of bacterial genomes, because the reference indexes are memory-intensive and base-level dynamic programming is slow. We present alamem (https://github.com/yunwilliamyu/alamem), an approximate local aligner that streams unprocessed reference databases and estimates average nucleotide identity (ANI) from Maximal-Exact-Match (MEM) chaining statistics. Alamem can query a bacterial genome against >85,000 prokaryotic genomes in under 30 seconds (with multithreading) using 4 GB of memory, making it over 16x faster and 21x more memory-efficient than existing local aligners using their default running modes. On top of alamem, we built alasight (https://github.com/graceoualline/alasight) for detecting signatures of horizontal gene transfer (HGT) by finding pairs of alamem hits to divergent genomes. Alasight achieves over an order of magnitude better sensitivity on data from real bovid microbiomes than existing mobile genetic element-detection software and provides depth and sparsity information supporting each putative HGT region.