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

Chenchen Peng

doi:10.1007/s11227-025-07184-z

2025-04-15

PRE

DOI：10.1007/s11227-025-07184-z

原文链接

原文求助

摘要

En 中文

泛基因组图代表多个个体的基因组，提供全面的参考并克服线性参考基因组中的等位基因偏差。序列到图的比对对于泛基因组任务至关重要，它将序列比对到图中以找到最佳匹配。然而，现有算法难以处理大规模序列。本文提出PVGwfa，一种多级并行序列到图的比对算法。我们首先采用MPI和Pthread进行多进程和多线程并行化。接下来，引入混合负载均衡策略以提高性能。此外，我们使用SIMD指令向量化PVGwfa的核心部分以加速序列比对。在真实和模拟数据集上的实验表明，PVGwfa将计算时间从近一小时缩短至几分钟。对于大型数据集，随着进程数从2增加到128，PVGwfa实现了1.98×到100.44×的加速比，同时保持了一致的比对结果。PVGwfa工具和源代码公开可访问于https://github.com/nudt-bioinfo/PVGwfa.git。

Keyword:

Sequence-to-graph alignment

MPI

Pthread

Bioinformatics

Read alignment

期刊

Journal of Supercomputing

IF:

2.7

论文数:

1.1K

被引数:

1.0W

机构

暂无机构信息

引用论文

A Greedy Algorithm for Aligning DNA Sequences 一种用于比对DNA序列的贪婪算法

Journal of Computational Biology

IF0

2000-02-01

PREAI

Zheng Zhang; Scott Schwartz; Lukas Wagner; Webb Miller

Pan-genomics in the human genome era 人类基因组时代的泛基因组学

NATURE REVIEWS GENETICS

IF52

2020-02-07

201

OAAI

Sherman, Rachel M.; Salzberg, Steven L.

Pangenome-based genome inference allows efficient and accurate genotyping across a wide spectrum of variant classes

NATURE GENETICS

IF31.8

2022-04-11

OAAI

Ebler, Jana; Ebert, Peter; Clarke, Wayne E.; Rausch, Tobias; Audano, Peter A.; Houwaart, Torsten; Mao, Yafei; Korbel, Jan O.; Eichler, Evan E.; Zody, Michael C.; Dilthey, Alexander T.; Marschall, Tobias

Evaluation of GRCh38 and de novo haploid genome assemblies demonstrates the enduring quality of the reference assembly GRCh38和从头单倍体基因组装配的评估证明了参考装配的持久质量

GENOME RESEARCH

IF5.5

2017-04-10

659

OAAI

Schneider, Valerie A.; Graves-Lindsay, Tina; Howe, Kerstin; Bouk, Nathan; Chen, Hsiu-Chuan; Kitts, Paul A.; Murphy, Terence D.; Pruitt, Kim D.; Thibaud-Nissen, Francoise; Albracht, Derek; Fulton, Robert S.; Kremitzki, Milinn; Magrini, Vincent; Markovic, Chris; McGrath, Sean; Steinberg, Karyn Meltz; Auger, Kate; Chow, William; Collins, Joanna; Harden, Glenn; Hubbard, Timothy; Pelan, Sarah; Simpson, Jared T.; Threadgold, Glen; Torrance, James; Wood, Jonathan M.; Clarke, Laura; Koren, Sergey; Boitano, Matthew; Peluso, Paul; Li, Heng; Chin, Chen-Shan; Phillippy, Adam M.; Durbin, Richard; Wilson, Richard K.; Flicek, Paul; Eichler, Evan E.; Church, Deanna M.

Optimal gap-affine alignment in O(s) space

Bioinformatics

IF0

2023-02-07

OAAI

Santiago Marco-Sola; Jordan M Eizenga; Andrea Guarracino; Benedict Paten; Erik Garrison; Miquel Moreto

The Sequence of the Human Genome 人类基因组的序列

Science

IF0

2001-02-16

PREAI

J. Craig Venter; Mark D. Adams; Eugene W. Myers; Peter W. Li; Richard J. Mural; Granger G. Sutton; Hamilton O. Smith; Mark Yandell; Cheryl A. Evans; Robert A. Holt; Jeannine D. Gocayne; Peter Amanatides; Richard M. Ballew; Daniel H. Huson; Jennifer Russo Wortman; Qing Zhang; Chinnappa D. Kodira; Xiangqun H. Zheng; Lin Chen; Marian Skupski; Gangadharan Subramanian; Paul D. Thomas; Jinghui Zhang; George L. Gabor Miklos; Catherine Nelson; Samuel Broder; Andrew G. Clark; Joe Nadeau; Victor A. McKusick; Norton Zinder; Arnold J. Levine; Richard J. Roberts; Mel Simon; Carolyn Slayman; Michael Hunkapiller; Randall Bolanos; Arthur Delcher; Ian Dew; Daniel Fasulo; Michael Flanigan; Liliana Florea; Aaron Halpern; Sridhar Hannenhalli; Saul Kravitz; Samuel Levy; Clark Mobarry; Knut Reinert; Karin Remington; Jane Abu-Threideh; Ellen Beasley; Kendra Biddick; Vivien Bonazzi; Rhonda Brandon; Michele Cargill; Ishwar Chandramouliswaran; Rosane Charlab; Kabir Chaturvedi; Zuoming Deng; Valentina Di Francesco; Patrick Dunn; Karen Eilbeck; Carlos Evangelista; Andrei E. Gabrielian; Weiniu Gan; Wangmao Ge; Fangcheng Gong; Zhiping Gu; Ping Guan; Thomas J. Heiman; Maureen E. Higgins; Rui-Ru Ji; Zhaoxi Ke; Karen A. Ketchum; Zhongwu Lai; Yiding Lei; Zhenya Li; Jiayin Li; Yong Liang; Xiaoying Lin; Fu Lu; Gennady V. Merkulov; Natalia Milshina; Helen M. Moore; Ashwinikumar K Naik; Vaibhav A. Narayan; Beena Neelam; Deborah Nusskern; Douglas B. Rusch; Steven Salzberg; Wei Shao; Bixiong Shue; Jingtao Sun; Zhen Yuan Wang; Aihui Wang; Xin Wang; Jian Wang; Ming-Hui Wei; Ron Wides; Chunlin Xiao; Chunhua Yan; Alison Yao; Jane Ye; Ming Zhan; Weiqing Zhang; Hongyu Zhang; Qi Zhao; Liansheng Zheng; Fei Zhong; Wenyan Zhong; Shiaoping C. Zhu; Shaying Zhao; Dennis Gilbert; Suzanna Baumhueter; Gene Spier; Christine Carter; Anibal Cravchik; Trevor Woodage; Feroze Ali; Huijin An; Aderonke Awe; Danita Baldwin; Holly Baden; Mary Barnstead; Ian Barrow; Karen Beeson; Dana Busam; Amy Carver; Angela Center; Ming Lai Cheng; Liz Curry; Steve Danaher; Lionel Davenport; Raymond Desilets; Susanne Dietz; Kristina Dodson; Lisa Doup; Steven Ferriera; Neha Garg; Andres Gluecksmann; Brit Hart; Jason Haynes; Charles Haynes; Cheryl Heiner; Suzanne Hladun; Damon Hostin; Jarrett Houck; Timothy Howland; Chinyere Ibegwam; Jeffery Johnson; Francis Kalush; Lesley Kline; Shashi Koduru; Amy Love; Felecia Mann; David May; Steven McCawley; Tina McIntosh; Ivy McMullen; Mee Moy; Linda Moy; Brian Murphy; Keith Nelson; Cynthia Pfannkoch; Eric Pratts; Vinita Puri; Hina Qureshi; Matthew Reardon; Robert Rodriguez; Yu-Hui Rogers; Deanna Romblad; Bob Ruhfel; Richard Scott; Cynthia Sitter; Michelle Smallwood; Erin Stewart; Renee Strong; Ellen Suh; Reginald Thomas; Ni Ni Tint; Sukyee Tse; Claire Vech; Gary Wang; Jeremy Wetter; Sherita Williams; Monica Williams; Sandra Windsor; Emily Winn-Deen; Keriellen Wolfe; Jayshree Zaveri; Karena Zaveri; Josep F. Abril; Roderic Guigó; Michael J. Campbell; Kimmen V. Sjolander; Brian Karlak; Anish Kejariwal; Huaiyu Mi; Betty Lazareva; Thomas Hatton; Apurva Narechania; Karen Diemer; Anushya Muruganujan; Nan Guo; Shinji Sato; Vineet Bafna; Sorin Istrail; Ross Lippert; Russell Schwartz; Brian Walenz; Shibu Yooseph; David Allen; Anand Basu; James Baxendale; Louis Blick; Marcelo Caminha; John Carnes-Stine; Parris Caulk; Yen-Hui Chiang; My Coyne; Carl Dahlke; Anne Deslattes Mays; Maria Dombroski; Michael Donnelly; Dale Ely; Shiva Esparham; Carl Fosler; Harold Gire; Stephen Glanowski; Kenneth Glasser; Anna Glodek; Mark Gorokhov; Ken Graham; Barry Gropman; Michael Harris; Jeremy Heil; Scott Henderson; Jeffrey Hoover; Donald Jennings; Catherine Jordan; James Jordan; John Kasha; Leonid Kagan; Cheryl Kraft; Alexander Levitsky; Mark Lewis; Xiangjun Liu; John Lopez; Daniel Ma; William Majoros; Joe McDaniel; Sean Murphy; Matthew Newman; Trung Nguyen; Ngoc Nguyen; Marc Nodell; Sue Pan; Jim Peck; Marshall Peterson; William Rowe; Robert Sanders; John Scott; Michael Simpson; Thomas Smith; Arlan Sprague; Timothy Stockwell; Russell Turner; Eli Venter; Mei Wang; Meiyuan Wen; David Wu; Mitchell Wu; Ashley Xia; Ali Zandieh; Xiaohong Zhu

Bit-parallel sequence-to-graph alignment

Bioinformatics

IF0

2019-03-09

OAAI

Mikko Rautiainen; Veli Mäkinen; Tobias Marschall

AnO(ND) difference algorithm and its variations

Algorithmica

IF0

1986-11-01

PREAI

Eugene W. Myers

Pangenomics enables genotyping of known structural variants in 5202 diverse genomes

Science

IF0

2021-12-17

OAAI

Jouni Sirén; Jean Monlong; Xian Chang; Adam M. Novak; Jordan M. Eizenga; Charles Markello; Jonas A. Sibbesen; Glenn Hickey; Pi-Chuan Chang; Andrew Carroll; Namrata Gupta; Stacey Gabriel; Thomas W. Blackwell; Aakrosh Ratan; Kent D. Taylor; Stephen S. Rich; Jerome I. Rotter; David Haussler; Erik Garrison; Benedict Paten

AStarix: Fast and Optimal Sequence-to-Graph Alignment AStarix：快速且最优的序列到图对齐

Lecture Notes in Computer Science

IF0

2020-04-21

OAAI

Pesho Ivanov; Benjamin Bichsel; Harun Mustafa; André Kahles; Gunnar Rätsch; Martin Vechev

查看更多内容