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

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. This paper 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 two-stage alignment process: (i) representing Maximum Exact Matches using a de Bruijn graph and clustering them based on their area; (ii) employing a de novo divide-and-conquer framework for alignment. 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.