MosaicLev: modified Levenshtein distance for mobile element-aware genome comparison

Genomes diverge, in part due to the activity of mobile elements, including elements that excise and reinsert (cut-paste) or propagate via an RNA intermediate (copy-paste). Standard sequence comparison methods are not motif-aware, penalizing mobile element insertions based on length rather than recognizing them as single biological events, while alignment-free methods still fail to adequately describe a known mobile-element sequence as a unified change.

We introduce a modified Levenshtein distance ( $\mathrm{mlev}$ ) that discounts specified block insertions via a tunable parameter ( $m\hspace{0.17em}\in \hspace{0.17em}[0,1]$ ): at $m=0$ it recovers ordinary Levenshtein distance and at $m=1$ a whole chunk acts like a single edit. On 67 Cluster G1 mycobacteriophage genomes (a viral group with MPME1 and MPME2), MPME1 targeting yielded $\sim 53\%$ discount for the 31-genome MPME1-score group and $\sim 9\%$ for the 11-genome MPME2-score group. MPME2 targeting reversed this pattern, with 18 phages low on both scores. For PV92, a 346-bp Yb8-containing insertion received 99.71% forward reduction at $m=1$ and none in reverse. Together, these results demonstrate that MosaicLev can quantify the contribution of known mobile elements to sequence differences across distinct genomic settings.

Python implementation with Numba JIT compilation freely available at https://doi.org/10.5281/zenodo.18452982.