Tomtom-lite: Accelerating Tomtom enables large-scale and real-time motif similarity scoring

Abstract

SummaryPairwise sequence similarity is a core operation in genomic analysis, yet most attention has been given to sequences made up of discrete characters. With the growing prevalence of machine learning, calculating similarities for sequences of continuous representations, e.g. frequency-based position-weight matrices (PWMs), attribution-based contribution-weight matrices, and even learned embeddings, is taking on newfound importance. Tomtom has previously been proposed as an algorithm for identifying pairs of PWMs whose similarity is statistically significant, but the implementation remains inefficient for both real-time and large-scale analysis. Accordingly, we have re-implemented Tomtom as a numba-accelerated Python function that is natively multi-threaded, avoids cache misses, more efficiently caches intermediate values, and uses approximations at compute bottlenecks. Here, we provide a detailed description of the original Tomtom method (see Supplementary Note 1) and present results demonstrating that our re-implementation can achieve over a thousand-fold speedup compared with the original tool on reasonable tasks (see Supplementary Note 2). Availability and ImplementationOur implementation of Tomtom is freely available as a Python package at https://github.com/jmschrei/memesuite-lite, which can be downloaded via pip install memelite.