EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Yanming Wei iD, Zhaoyang Huang iD, Pinglu Zhang iD, Yizheng Wang iD, Yan Li, Liang Yu iD, Quan Zou iD

GigaScience · 21.01.2026 · 15

DOI: 10.1093/gigascience/giaf163 ↗

Kurz gefasst

Fachartikel in der Zeitschrift GigaScience, online erschienen am 05.01.2026. Verfasst von Yanming Wei und 6 weiteren Autor:innen. Beteiligte Einrichtung: School of Computer Science and Technology, Xidian University, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xi'an, 710126, China. Hauptthemen laut MEDLINE: Sequence Alignment, Software, Sequence Analysis, DNA, Computational Biology. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Xidian University.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Sequence AlignmentSoftwareSequence Analysis, DNAComputational BiologyAlgorithmsGenomics

Stichwörter der Autor:innen

de Bruijn graphmaximum exact matchmultiple sequence alignmentparallel algorithm design

Autor:innen und Institutionen

  • School of Computer Science and Technology, Xidian University, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xi'an, 710126, China.
  • Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China, University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zo…
  • Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, No. 2006, Xiyuan Avenue, Pidu Zone, Chengdu, 610054, China.
  • School of Management, Xi'an Polytechnic University, No.19, Jinhua South Road, Xi'an, 710048, China.

ORCID-Profile: Yanming Wei, Zhaoyang Huang, Pinglu Zhang, Yizheng Wang, Liang Yu, Quan Zou

Förderung

  • National Natural Science Foundation of China
  • Xidian University

Zitieren

APA

Wei, Y., Huang, Z., Zhang, P., Wang, Y., Li, Y., Yu, L., & Zou, Q. (2026). deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment. GigaScience, 15. https://doi.org/10.1093/gigascience/giaf163

Vancouver

Wei Y, Huang Z, Zhang P, Wang Y, Li Y, Yu L, et al. deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment. GigaScience. 2026;15. doi:10.1093/gigascience/giaf163

BibTeX
@article{Wei2026,
  author = {Wei, Yanming and Huang, Zhaoyang and Zhang, Pinglu and Wang, Yizheng and Li, Yan and Yu, Liang and Zou, Quan},
  title = {deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment},
  journal = {GigaScience},
  year = {2026},
  volume = {15},
  doi = {10.1093/gigascience/giaf163}
}
Kostenlos starten →