deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment

BACKGROUND: Multiple sequence alignment (MSA) continues to be a central challenge in comparative genomics, where the quality of alignment plays a crucial role in determining the accuracy of downstream analyses. However, the challenge of large-scale alignment remains significant. FINDINGS: This article introduces deMEM, a novel and effective framework for DNA multiple sequence alignment, which enables existing MSA methods such as MAFFT to handle extremely large sequences. deMEM is a 3-stage alignment process: (i) representing maximum exact matches using a de Bruijn graph and clustering them based on their area, (ii) employing a novel divide-and-conquer framework for alignment, and (iii) providing profile-profile alignment between different clusters. CONCLUSIONS: DeMEM enables existing methods like MAFFT to align an extremely large number of sequences, including long sequences that cannot be directly aligned, such as those in a dataset of a thousand monkeypox virus genomes. The deMEM package is free and available at https://github.com/malabz/deMEM.