FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity
Briefings in Bioinformatics · 2024
DOI: 10.1093/bib/bbaf061 ↗Kurz gefasst
Fachartikel in der Zeitschrift Briefings in Bioinformatics, 2024. Verfasst von Yanming Wei und 4 weiteren Autor:innen. Beteiligte Einrichtung: School of Computer Science and Technology, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xidian University, Xi'an 710126, China. Hauptthemen laut MEDLINE: Algorithms, Computational Biology, Sequence Alignment, Sequence Analysis, DNA. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0). Gefördert von: Xidian University, National Natural Science Foundation of China.
Abstract (Originalsprache)
Pairwise sequence alignment (PSA) serves as the cornerstone in computational bioinformatics, facilitating multiple sequence alignment and phylogenetic analysis. This paper introduces the FORAlign algorithm, leveraging the Four Russians algorithm with identical upper-bound time and space complexity as the Hirschberg divide-and-conquer PSA algorithm, aimed at accelerating Hirschberg PSA algorithm in parallel. Particularly notable is its capability to achieve up to 16.79 times speedup when aligning sequences with low sequence similarity, compared to the conventional Needleman-Wunsch PSA method using non-heuristic methods. Empirical evaluations underscore FORAlign’s superiority over existing wavefront alignment (WFA) series software, especially in scenarios characterized by low sequence similarity during PSA tasks. Our method is capable of directly aligning monkeypox sequences with other sequences using non-heuristic methods. The algorithm was implemented within the FORAlign library, providing functionality for PSA and foundational support for multiple sequence alignment and phylogenetic trees. The FORAlign library is freely available at https://github.com/malabz/FORAlign.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Computer Science and Technology, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xidian University, Xi'an 710126, China.
- Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zone, Quzhou 324003, China.
- Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, No. 2006, Xiyuan Avenue, Pidu Zone, Chengdu 610054, China.
ORCID-Profile: Yanming Wei, Liang Yu, Quan Zou
Förderung
- Xidian University
- National Natural Science Foundation of China
Zitieren
APA
Wei, Y., Zhou, T., Zhai, Y., Yu, L., & Zou, Q. (2024). FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity. Briefings in Bioinformatics. https://doi.org/10.1093/bib/bbaf061
Vancouver
Wei Y, Zhou T, Zhai Y, Yu L, Zou Q. FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity. Briefings in Bioinformatics. 2024. doi:10.1093/bib/bbaf061
BibTeX
@article{Wei2024,
author = {Wei, Yanming and Zhou, Tong and Zhai, Yixiao and Yu, Liang and Zou, Quan},
title = {FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity},
journal = {Briefings in Bioinformatics},
year = {2024},
doi = {10.1093/bib/bbaf061}
}
EUVIMED