Haplotype-Based Parallel PBWT for Biobank Scale Data

doi:10.1007/978-3-032-02489-3_10

2026-01-01

PRE

张绍杰 (Shaojie Zhang) *

DOI：10.1007/978-3-032-02489-3_10

原文链接

原文求助

摘要

En 中文

Durbin的基于位置Burrows-Wheeler变换（PBWT）使得在包含M个单倍型和N个变异位点的群体面板中报告所有单倍型间的匹配具有最优时间复杂度O(MN)。然而，当单倍型数量达到数百万时，即使这种效率仍可能过慢。为了进一步降低运行时间，本文介绍了一种用于所有单倍型间匹配的PBWT算法的并行版本，称为HP-PBWT（基于单倍型的并行PBWT）。HP-PBWT通过将单倍型面板分割为单倍型块来并行执行PBWT。HP-PBWT算法在保持内存效率的同时，实现了PBWT构建、报告所有单倍型间的L长匹配以及报告所有单倍型间的集合最大匹配的并行化。HP-PBWT在PBWT构建中的时间复杂度为O((M/T + T)N)，在报告所有单倍型间的L长匹配和集合最大匹配中的时间复杂度为O((M/T + T + c*)N)，其中T为线程数，c*为每个位点每个单倍型的最大匹配数（对于L长匹配为长度L的匹配数，对于集合最大匹配为最大分歧值）。在包含UK Biobank基因分型阵列数据的IO包含基准测试中，HP-PBWT使用30个线程实现了4倍加速。当将HP-PBWT应用于包含800万个随机单倍型（等长随机二进制字符串）的IO排除基准测试时，在Amazon EC2服务器上使用60个核心可达到22倍加速。通过进一步硬件优化，HP-PBWT有望高效处理数十亿个单倍型。

Keyword:

PBWT

Parallel Computing

Haplotype Matching

期刊

COMPUTATIONAL ADVANCES IN BIO AND MEDICAL SCIENCES, ICCABS 2025

IF:

论文数:

被引数:

机构

State University System of Florida

学者数:

12.8W

论文数: 10.9W

被引数: 130

University of Central Florida

学者数:

8.7K

论文数: 6.8K

被引数: 1.4W

引用论文

Scans as primitive parallel operations

IEEE Transactions on Computers

IF0

1989-01-01

PREAI

G.E. Blelloch

Study on the thermal dissipation performance of GPU cooling system with nanofluid as coolant

CASE STUDIES IN THERMAL ENGINEERING

IF6.4

2021-06-01

OAAI

Siricharoenpanich, A.; Wiriyasart, S.; Naphon, P.

Sequencing of 53,831 diverse genomes from the NHLBI TOPMed Program 来自NHLBI TOPMed程序的53,831个不同基因组的测序

Nature

IF0

2021-02-10

OAAI

Daniel Taliun; Daniel N. Harris; Michael D. Kessler; Jedidiah Carlson; Zachary A. Szpiech; Raul Torres; Sarah A. Gagliano Taliun; André Corvelo; Stephanie M. Gogarten; Hyun Min Kang; Achilleas N. Pitsillides; Jonathon LeFaive; Seung-been Lee; Xiaowen Tian; Brian L. Browning; Sayantan Das; Anne-Katrin Emde; Wayne E. Clarke; Douglas P. Loesch; Amol C. Shetty; Thomas W. Blackwell; Albert V. Smith; Quenna Wong; Xiaoming Liu; Matthew P. Conomos; Dean M. Bobo; François Aguet; Christine Albert; Alvaro Alonso; Kristin G. Ardlie; Dan E. Arking; Stella Aslibekyan; Paul L. Auer; John Barnard; R. Graham Barr; Lucas Barwick; Lewis C. Becker; Rebecca L. Beer; Emelia J. Benjamin; Lawrence F. Bielak; John Blangero; Michael Boehnke; Donald W. Bowden; Jennifer A. Brody; Esteban G. Burchard; Brian E. Cade; James F. Casella; Brandon Chalazan; Daniel I. Chasman; Yii-Der Ida Chen; Michael H. Cho; Seung Hoan Choi; Mina K. Chung; Clary B. Clish; Adolfo Correa; Joanne E. Curran; Brian Custer; Dawood Darbar; Michelle Daya; Mariza de Andrade; Dawn L. DeMeo; Susan K. Dutcher; Patrick T. Ellinor; Leslie S. Emery; Celeste Eng; Diane Fatkin; Tasha Fingerlin; Lukas Forer; Myriam Fornage; Nora Franceschini; Christian Fuchsberger; Stephanie M. Fullerton; Soren Germer; Mark T. Gladwin; Daniel J. Gottlieb; Xiuqing Guo; Michael E. Hall; Jiang He; Nancy L. Heard-Costa; Susan R. Heckbert; Marguerite R. Irvin; Jill M. Johnsen; Andrew D. Johnson; Robert Kaplan; Sharon L. R. Kardia; Tanika Kelly; Shannon Kelly; Eimear E. Kenny; Douglas P. Kiel; Robert Klemmer; Barbara A. Konkle; Charles Kooperberg; Anna Köttgen; Leslie A. Lange; Jessica Lasky-Su; Daniel Levy; Xihong Lin; Keng-Han Lin; Chunyu Liu; Ruth J. F. Loos; Lori Garman; Robert Gerszten; Steven A. Lubitz; Kathryn L. Lunetta; Angel C. Y. Mak; Ani Manichaikul; Alisa K. Manning; Rasika A. Mathias; David D. McManus; Stephen T. McGarvey; James B. Meigs; Deborah A. Meyers; Julie L. Mikulla; Mollie A. Minear; Braxton D. Mitchell; Sanghamitra Mohanty; May E. Montasser; Courtney Montgomery; Alanna C. Morrison; Joanne M. Murabito; Andrea Natale; Pradeep Natarajan; Sarah C. Nelson; Kari E. North; Jeffrey R. O’Connell; Nicholette D. Palmer; Nathan Pankratz; Gina M. Peloso; Patricia A. Peyser; Jacob Pleiness; Wendy S. Post; Bruce M. Psaty; D. C. Rao; Susan Redline; Alexander P. Reiner; Dan Roden; Jerome I. Rotter; Ingo Ruczinski; Chloé Sarnowski; Sebastian Schoenherr; David A. Schwartz; Jeong-Sun Seo; Sudha Seshadri; Vivien A. Sheehan; Wayne H. Sheu; M. Benjamin Shoemaker; Nicholas L. Smith; Jennifer A. Smith; Nona Sotoodehnia; Adrienne M. Stilp; Weihong Tang; Kent D. Taylor; Marilyn Telen; Timothy A. Thornton; Russell P. Tracy; David J. Van Den Berg; Ramachandran S. Vasan; Karine A. Viaud-Martinez; Scott Vrieze; Daniel E. Weeks; Bruce S. Weir; Scott T. Weiss; Lu-Chen Weng; Cristen J. Willer; Yingze Zhang; Xutong Zhao; Donna K. Arnett; Allison E. Ashley-Koch; Kathleen C. Barnes; Eric Boerwinkle; Stacey Gabriel; Richard Gibbs; Kenneth M. Rice; Stephen S. Rich; Edwin K. Silverman; Pankaj Qasba; Weiniu Gan; Namiko Abe; Laura Almasy; Seth Ament; Peter Anderson; Pramod Anugu; Deborah Applebaum-Bowden; Tim Assimes; Dimitrios Avramopoulos; Emily Barron-Casella; Terri Beaty; Gerald Beck; Diane Becker; Amber Beitelshees; Takis Benos; Marcos Bezerra; Joshua Bis; Russell Bowler; Ulrich Broeckel; Jai Broome; Karen Bunting; Carlos Bustamante; Erin Buth; Jonathan Cardwell; Vincent Carey; Cara Carty; Richard Casaburi; Peter Castaldi; Mark Chaffin; Christy Chang; Yi-Cheng Chang; Sameer Chavan; Bo-Juen Chen; Wei-Min Chen; Lee-Ming Chuang; Ren-Hua Chung; Suzy Comhair; Elaine Cornell; Carolyn Crandall; James Crapo; Jeffrey Curtis; Coleen Damcott; Sean David; Colleen Davis; Lisa de las Fuentes; Michael DeBaun; Ranjan Deka; Scott Devine; Qing Duan; Ravi Duggirala; Jon Peter Durda; Charles Eaton; Lynette Ekunwe; Adel El Boueiz; Serpil Erzurum; Charles Farber; Matthew Flickinger; Myriam Fornage; Chris Frazar; Mao Fu; Lucinda Fulton; Shanshan Gao; Yan Gao; Margery Gass; Bruce Gelb; Xiaoqi Priscilla Geng; Mark Geraci; Auyon Ghosh; Chris Gignoux; David Glahn; Da-Wei Gong; Harald Goring; Sharon Graw; Daniel Grine; C. Charles Gu; Yue Guan; Namrata Gupta; Jeff Haessler; Nicola L. Hawley; Ben Heavner; David Herrington; Craig Hersh; Bertha Hidalgo; James Hixson; Brian Hobbs; John Hokanson; Elliott Hong; Karin Hoth; Chao Agnes Hsiung; Yi-Jen Hung; Haley Huston; Chii Min Hwu; Rebecca Jackson; Deepti Jain; Min A. Jhun; Craig Johnson; Rich Johnston; Kimberly Jones; Sekar Kathiresan; Alyna Khan; Wonji Kim; Greg Kinney; Holly Kramer; Christoph Lange; Ethan Lange; Leslie Lange; Cecelia Laurie; Meryl LeBoff; Jiwon Lee; Seunggeun Shawn Lee; Wen-Jane Lee; David Levine; Joshua Lewis; Xiaohui Li; Yun Li; Henry Lin; Honghuang Lin; Keng Han Lin; Simin Liu; Yongmei Liu; Yu Liu; James Luo; Michael Mahaney; Barry Make; JoAnn Manson; Lauren Margolin; Lisa Martin; Susan Mathai; Susanne May; Patrick McArdle; Merry-Lynn McDonald; Sean McFarland; Daniel McGoldrick; Caitlin McHugh; Hao Mei; Luisa Mestroni; Nancy Min; Ryan L. Minster; Matt Moll; Arden Moscati; Solomon Musani; Stanford Mwasongwe; Josyf C. Mychaleckyj; Girish Nadkarni; Rakhi Naik; Take Naseri; Sergei Nekhai; Bonnie Neltner; Heather Ochs-Balcom; David Paik; James Pankow; Afshin Parsa; Juan Manuel Peralta; Marco Perez; James Perry; Ulrike Peters; Lawrence S. Phillips; Toni Pollin; Julia Powers Becker; Meher Preethi Boorgula; Michael Preuss; Dandi Qiao; Zhaohui Qin; Nicholas Rafaels; Laura Raffield; Laura Rasmussen-Torvik; Aakrosh Ratan; Robert Reed; Elizabeth Regan; Muagututi‘a Sefuiva Reupena; Carolina Roselli; Pamela Russell; Sarah Ruuska; Kathleen Ryan; Ester Cerdeira Sabino; Danish Saleheen; Shabnam Salimi; Steven Salzberg; Kevin Sandow; Vijay G. Sankaran; Christopher Scheller; Ellen Schmidt; Karen Schwander; Frank Sciurba; Christine Seidman; Jonathan Seidman; Stephanie L. Sherman; Aniket Shetty; Wayne Hui-Heng Sheu; Brian Silver; Josh Smith; Tanja Smith; Sylvia Smoller; Beverly Snively; Michael Snyder; Tamar Sofer; Garrett Storm; Elizabeth Streeten; Yun Ju Sung; Jody Sylvia; Adam Szpiro; Carole Sztalryd; Hua Tang; Margaret Taub; Matthew Taylor; Simeon Taylor; Machiko Threlkeld; Lesley Tinker; David Tirschwell; Sarah Tishkoff; Hemant Tiwari; Catherine Tong; Michael Tsai; Dhananjay Vaidya; Peter VandeHaar; Tarik Walker; Robert Wallace; Avram Walts; Fei Fei Wang; Heming Wang; Karol Watson; Jennifer Wessel; Kayleen Williams; L. Keoki Williams; Carla Wilson; Joseph Wu; Huichun Xu; Lisa Yanek; Ivana Yang; Rongze Yang; Norann Zaghloul; Maryam Zekavat; Snow Xueyan Zhao; Wei Zhao; Degui Zhi; Xiang Zhou; Xiaofeng Zhu; George J. Papanicolaou; Deborah A. Nickerson; Sharon R. Browning; Michael C. Zody; Sebastian Zöllner; James G. Wilson; L. Adrienne Cupples; Cathy C. Laurie; Cashell E. Jaquish; Ryan D. Hernandez; Timothy D. O’Connor; Gonçalo R. Abecasis

HTSlib: C library for reading/writing high-throughput sequencing data 用于读取/写入高通量测序数据的HTSlib: C库

GIGASCIENCE

IF3.9

2021-02-16

171

OAAI

Bonfield, James K.; Marshall, John; Danecek, Petr; Li, Heng; Ohan, Valeriu; Whitwham, Andrew; Keane, Thomas; Davies, Robert M.

23andMe: a new two-sided data-banking market model

BMC MEDICAL ETHICS

IF3.1

2016-03-31

OAAI

Stoekle, Henri-Corto; Mamzer-Bruneel, Marie-France; Vogt, Guillaume; Herve, Christian

Speedup versus efficiency in parallel systems

IEEE Transactions on Computers

IF0

1989-03-01

PREAI

D.L. Eager; J. Zahorjan; E.D. Lazowska

Fast and Robust Identity-by-Descent Inference with the Templated Positional Burrows-Wheeler Transform

MOLECULAR BIOLOGY AND EVOLUTION

IF5.3

2020-12-23

OAAI

Freyman, William A.; McManus, Kimberly F.; Shringarpure, Suyash S.; Jewett, Ethan M.; Bryc, Katarzyna; Auton, Adam

CPU Overclocking: A Performance Assessment of Air, Cold Plates, and Two-Phase Immersion Cooling

IEEE Transactions on Components, Packaging and Manufacturing Technology

IF0

2021-10-01

OAAI

Bharath Ramakrishnan; Husam Alissa; Ioannis Manousakis; Robert Lankston; Ricardo Bianchini; Washington Kim; Rich Baca; Pulkit A. Misra; Inigo Goiri; Majid Jalili; Ashish Raniwala; Brijesh Warrier; Mark Monroe; Christian Belady; Mark Shaw; Marcus Fontoura

What is ancestry?

PLOS GENETICS

IF3.7

2020-03-09

104

OAAI

Mathieson, Iain; Scally, Aylwyn

UK Biobank: An Open Access Resource for Identifying the Causes of a Wide Range of Complex Diseases of Middle and Old Age 英国生物银行: 一个开放获取的资源，用于识别各种复杂的中老年疾病的原因

PLOS MEDICINE

IF9.9

2015-03-31

6.7K

OAAI

Sudlow, Cathie; Gallacher, John; Allen, Naomi; Beral, Valerie; Burton, Paul; Danesh, John; Downey, Paul; Elliott, Paul; Green, Jane; Landray, Martin; Liu, Bette; Matthews, Paul; Ong, Giok; Pell, Jill; Silman, Alan; Young, Alan; Sprosen, Tim; Peakman, Tim; Collins, Rory

查看更多内容