EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity

Yanming Wei iD, Tong Zhou, Yixiao Zhai, Liang Yu iD, Quan Zou iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsComputational BiologySequence AlignmentSequence Analysis, DNASoftwareHumans

Stichwörter der Autor:innen

dynamic programmingfour Russians speedupparallel algorithm designsequence alignment

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}
}
Kostenlos starten →