Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT).
Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT).
复制标题
DOI：
10.1093/bioinformatics/btu014
复制
发表时间：
2014-05-01
期刊：
影响因子：
--
通讯作者：
Durbin R
中科院分区：
文献类型：
--
作者：
Durbin R
动机：在过去的几年中，基于使用Burrows-Wheeler变换的后缀阵列的方法已被广泛用于DNA序列读取匹配和组装。这些提供了非常快速的搜索算法，在搜索模式大小上是线性的，对被搜索的数据集的高度可压缩表示。同时，基因型数据的算法开发集中在用于定相和插补的统计方法上，基于与参考数据的隐马尔可夫模型表示的概率匹配，其虽然强大但计算效率低得多。在这里，单倍型匹配的理论，使用后缀数组的想法，这应该规模太大的数据集比目前处理的基因型算法。结果如下：给出了一种基于位置前缀数组的O（NM）算法，即位置Burrows-Wheeler变换（PBWT）。在大型数据集上，这比使用gzip对原始数据进行压缩要小一百倍以上。使用这种表示的方法，以找到所有最大单倍型匹配内的集合在O（NM）的时间，而不是O（NM 2）从天真的成对比较预期，也是一个快速算法，经验上独立于M给出足够的内存索引，找到一个新的序列和集合之间的最大匹配。讨论包括关于如何将这些方法用于估算和分阶段的一些建议。联系人：richard. sanger.ac.uk http://github.com/richarddurbin/pbwt
Motivation: Over the last few years, methods based on suffix arrays using the Burrows–Wheeler Transform have been widely used for DNA sequence read matching and assembly. These provide very fast search algorithms, linear in the search pattern size, on a highly compressible representation of the dataset being searched. Meanwhile, algorithmic development for genotype data has concentrated on statistical methods for phasing and imputation, based on probabilistic matching to hidden Markov model representations of the reference data, which while powerful are much less computationally efficient. Here a theory of haplotype matching using suffix array ideas is developed, which should scale too much larger datasets than those currently handled by genotype algorithms. Results: Given M sequences with N bi-allelic variable sites, an O(NM) algorithm to derive a representation of the data based on positional prefix arrays is given, which is termed the positional Burrows–Wheeler transform (PBWT). On large datasets this compresses with run-length encoding by more than a factor of a hundred smaller than using gzip on the raw data. Using this representation a method is given to find all maximal haplotype matches within the set in O(NM) time rather than O(NM2) as expected from naive pairwise comparison, and also a fast algorithm, empirically independent of M given sufficient memory for indexes, to find maximal matches between a new sequence and the set. The discussion includes some proposals about how these approaches could be used for imputation and phasing. Availability: http://github.com/richarddurbin/pbwt Contact: richard.durbin@sanger.ac.uk
登录
查看更多内容
来自1,092个人基因组的遗传变异的综合图。
影响因子：
64.8
作者：
通讯作者：
--
影响因子：
12.3
作者：
Langmead B;Trapnell C;Pop M;Salzberg SL
通讯作者：
Salzberg SL
影响因子：
48
作者：
Delaneau, Olivier;Marchini, Jonathan;Zagury, Jean-Francois
通讯作者：
Zagury, Jean-Francois
SOAP2：改进的超快工具，用于短读对齐
影响因子：
5.8
作者：
Li, Ruiqiang;Yu, Chang;Wang, Jun
通讯作者：
Wang, Jun
影响因子：
4.4
作者：
Hoffmann, Thomas J.;Zhan, Yiping;Risch, Neil
通讯作者：
Risch, Neil