d-PBWT: dynamic positional Burrows-Wheeler transform
d-PBWT: dynamic positional Burrows-Wheeler transform
复制标题
DOI：
10.1093/bioinformatics/btab117
复制
发表时间：
2021-02-24
期刊：
影响因子：
5.8
通讯作者：
Zhang, Shaojie
中科院分区：
文献类型：
--
作者：
Sanaullah, Ahsan;Zhi, Degui;Zhang, Shaojie
动机：Durbin的位置Burrows-Wheeler变换（PBWT）是用于单倍型匹配的可扩展数据结构。它已成功地应用于同源（IBD）片段鉴定和基因型插补。一旦构建了单倍型组的PBWT，它支持所有个体之间的所有共享长片段（长匹配）的高效检索以及外部单倍型和组之间的高效查询。然而，标准的PBWT是一个基于数组的静态数据结构，不支持动态更新的panel.Results：在这里，我们概括了静态PBWT的动态数据结构，d-PBWT，在每个位置的反向前缀排序存储与链表。我们还开发了有效的算法插入和删除个别单倍型。此外，我们还验证了d-PBWT可以支持PBWT的所有算法。在此过程中，我们系统地研究了集合最大匹配和长匹配查询算法的变化：虽然它们都具有独立于数据库大小的平均情况时间复杂度，但它们具有不同的最坏情况复杂度和对其他数据结构的依赖性。
Motivation: Durbin's positional Burrows-Wheeler transform (PBWT) is a scalable data structure for haplotype matching. It has been successfully applied to identical by descent (IBD) segment identification and genotype imputation. Once the PBWT of a haplotype panel is constructed, it supports efficient retrieval of all shared long segments among all individuals (long matches) and efficient query between an external haplotype and the panel. However, the standard PBWT is an array-based static data structure and does not support dynamic updates of the panel.Results: Here, we generalize the static PBWT to a dynamic data structure, d-PBWT, where the reverse prefix sorting at each position is stored with linked lists. We also developed efficient algorithms for insertion and deletion of individual haplotypes. In addition, we verified that d-PBWT can support all algorithms of PBWT. In doing so, we systematically investigated variations of set maximal match and long match query algorithms: while they all have average case time complexity independent of database size, they have different worst case complexities and dependencies on additional data structures.