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 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.

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.