Scholarlink

<p>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.98<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7184_Article_IEq1.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\times\)</EquationSource> <EquationSource Format="MATHML"><math> <mo>×</mo> </math></EquationSource> </InlineEquation> to 100.44<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7184_Article_IEq2.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\times\)</EquationSource> <EquationSource Format="MATHML"><math> <mo>×</mo> </math></EquationSource> </InlineEquation> 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 <a href="https://github.com/nudt-bioinfo/PVGwfa.git">https://github.com/nudt-bioinfo/PVGwfa.git</a>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

PVGwfa: a multi-level parallel sequence-to-graph alignment algorithm

  • 期刊论文

  • 发表日期：

    2025年4月15日

查看全文
  • Chenchen Peng,
  • Zeyu Xia,
  • Shengbo Tang,
  • Yifei Guo,
  • Canqun Yang,
  • Tao Tang,
  • Yingbo Cui

摘要

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.98 \(\times\) × to 100.44 \(\times\) × 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.