Min-frame transformation enables more sensitive viral genome alignment
Preprint
Abstract
Motivation: Maximal unique matches (MUMs) are a fundamental primitive in genome comparison, where they serve as high-confidence anchors for downstream multiple genome alignment. However, because MUMs rely on exact string matching, their effectiveness degrades with increased genome divergence and larger sets of genomes, inhibiting their ability to recover long homologous regions and reducing the number of base pairs covered by the multiple genome alignment. Additionally, existing approaches that improve robustness to mutation, such as spaced seeds or translated alignment methods, introduce trade-offs in specificity, scalability, or computational complexity. Methods: To address this gap, we introduce the Min-Frame Transformation (MFT), a deterministic encoding of nucleotide sequences to sequences over a transformed alphabet that preserves the coordinate structure of the original sequence. At each position, the MFT selects a k -mer from a local window according to a fixed global ordering and assigns it a character in the transformed alphabet via a predefined mapping. This process captures local sequence context and can mask the impact of mutations, increasing the likelihood that homologous regions remain detectable as exact matches. The resulting transformed sequences can be indexed using standard string data structures, such as suffix arrays and suffix trees, enabling efficient extraction of MUMs without modifying existing algorithms. Impact: The MFT is a novel computational approach for improving the robustness of MUM-based seeding for genome alignment by producing longer and more contiguous matches that span a greater fraction of the genome, leading to improved alignment coverage and SNP recall. Altogether, these improvements have the potential to result in improvements for downstream viral genome analysis applications such as phylogenetic inference and transmission analysis. Funding: Tandy Warnow : NSF grant 2316233 Todd J. Treangen : NSF grants 2126387, 2239114, NIH grants U19-AI144297, P01-AI152999Keywords
This publication has 42 references indexed in Scilit:
- Strain-level transmission inference across multi-kingdom metagenomic data using TRACSNature Microbiology, 2026
- Evolution shapes and conserves genomic signatures in virusesCommunications Biology, 2024
- Genetic conservation across SARS-CoV-2 non-structural proteins – Insights into possible targets for treatment of future viral outbreaksVirology, 2023
- The Statistics of k -mers from a Sequence Undergoing a Simple Mutation Process Without Spurious MatchesJournal of Computational Biology, 2022
- Theory of local k-mer selection with applications to long-read alignmentBioinformatics, 2021
- Epidemiological data and genome sequencing reveals that nosocomial transmission of SARS-CoV-2 is underestimated and mostly mediated by a small number of highly infectious individualsJournal of Infection, 2021
- MMseqs2 enables sensitive protein sequence searching for the analysis of massive data setsNature Biotechnology, 2017
- PatternHunter: faster and more sensitive homology searchBioinformatics, 2002
- Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic treesBioinformatics, 1997
- Successes, runs and longest runsStatistics & Probability Letters, 1986