Syllable-PBWT for space-efficient haplotype long-match query.
Syllable-PBWT for space-efficient haplotype long-match query.
复制标题
DOI：
10.1093/bioinformatics/btac734
复制
发表时间：
2023-01-01
期刊：
影响因子：
--
通讯作者：
Zhi D
中科院分区：
文献类型：
--
作者：
Wang V;Naseri A;Zhang S;Zhi D
位置Burrows-Wheeler变换（PBWT）在生物库规模数据的单倍型匹配方面取得了巨大进步。对于遗传谱系搜索，基于PBWT的方法优化了查找查询单倍型和预定义的单倍型面板之间的长匹配的渐近运行时间。然而，为了实现快速查询搜索，全尺寸面板和PBWT数据结构必须保存在内存中，防止现有算法扩展到由数百万单倍型组成的现代生物库面板。在这项工作中，我们提出了一个空间有效的PBWT命名为音节PBWT，它将每个单倍型分为音节，建立PBWT位置前缀数组的压缩音节面板，并利用多项式滚动哈希函数的位置子串比较。在此基础上，提出了一种基于Syllable-PBWT的长匹配查询算法Syllable-Query。与之前发表的最具时间和空间效率的长匹配查询问题解决方案相比，音节查询在UK Biobank基因型数据和1000个基因组计划序列数据上将内存使用减少了100倍以上。令人惊讶的是，音节数据结构的较小尺寸允许更有效的迭代和CPU缓存使用，从而使音节查询比现有解决方案更快地运行。 https://github.com/ZhiGroup/Syllable-PBWT 补充数据可在Bioinformatics在线获得。
The positional Burrows–Wheeler transform (PBWT) has led to tremendous strides in haplotype matching on biobank-scale data. For genetic genealogical search, PBWT-based methods have optimized the asymptotic runtime of finding long matches between a query haplotype and a predefined panel of haplotypes. However, to enable fast query searches, the full-sized panel and PBWT data structures must be kept in memory, preventing existing algorithms from scaling up to modern biobank panels consisting of millions of haplotypes. In this work, we propose a space-efficient variation of PBWT named Syllable-PBWT, which divides every haplotype into syllables, builds the PBWT positional prefix arrays on the compressed syllabic panel, and leverages the polynomial rolling hash function for positional substring comparison. With the Syllable-PBWT data structures, we then present a long match query algorithm named Syllable-Query. Compared to the most time- and space-efficient previously published solution to the long match query problem, Syllable-Query reduced the memory use by a factor of over 100 on both the UK Biobank genotype data and the 1000 Genomes Project sequence data. Surprisingly, the smaller size of our syllabic data structures allows for more efficient iteration and CPU cache usage, granting Syllable-Query even faster runtime than existing solutions. https://github.com/ZhiGroup/Syllable-PBWT Supplementary data are available at Bioinformatics online.
登录
查看更多内容
影响因子：
10.7
作者：
Freyman WA;McManus KF;Shringarpure SS;Jewett EM;Bryc K;23 and Me Research Team;Auton A
通讯作者：
Auton A
影响因子：
30.8
作者：
Loh, Po-Ru;Danecek, Petr;Palamara, Pier Francesco;Fuchsberger, Christian;Reshef, Yakir A.;Finucane, Hilary K.;Schoenherr, Sebastian;Forer, Lukas;McCarthy, Shane;Abecasis, Goncalo R.;Durbin, Richard;Price, Alkes L.
通讯作者：
Price, Alkes L.
影响因子：
4.5
作者：
Rubinacci S;Delaneau O;Marchini J
通讯作者：
Marchini J
影响因子：
5.8
作者：
Sanaullah, Ahsan;Zhi, Degui;Zhang, Shaojie
通讯作者：
Zhang, Shaojie
影响因子：
1.2
作者：
Alomair, Basel;Clark, Andrew;Poovendran, Radha
通讯作者：
Poovendran, Radha