.png){kind=icon}
.png){kind=icon}
Return
PVGwfa: a multi-level parallel sequence-to-graph alignment algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/s11227-025-07184-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A pangenome graph represents the genomes of multiple individuals, offering a comprehensive reference and overcoming allele bias from linear reference genomes. Sequence-to-graph alignment, crucial for pangenome tasks, aligns sequences to a graph to find the best matches. However, existing algorithms struggle with large-scale sequences. In this paper, we propose PVGwfa, a multi-level parallel sequence-to-graph alignment algorithm. We first employ MPI and Pthread for multi-process and multi-thread parallelization. Next, we introduce a hybrid load balancing strategy for better performance. Additionally, we vectorize the core of PVGwfa using SIMD instructions to accelerate sequence alignment. Experiments on real and simulated datasets show that PVGwfa reduces computation time from nearly an hour to a few minutes. For large datasets, PVGwfa achieved speedups ranging from 1.98x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document} to 100.44x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document} as the number of processes increased from 2 to 128, while maintaining consistent alignment results. The PVGwfa tool and source code are publicly available at https://github.com/nudt-bioinfo/PVGwfa.git.
Keywords:
Sequence-to-graph alignment
MPI
Pthread
Bioinformatics
Read alignment
Journal
IF:
2.7
Papers:
1.0K
Citations:
1.0W
Organization
No organization information available