Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
复制标题
DOI：
10.1093/bioinformatics/bts173
复制
发表时间：
2012-06-01
期刊：
影响因子：
5.8
通讯作者：
Rosone, Giovanna
中科院分区：
文献类型：
--
作者：
Cox, Anthony J.;Bauer, Markus J.;Rosone, Giovanna
动机：Burrows-Wheeler 变换 (BWT) 是许多文本数据压缩和索引算法的基础，但是计算非常大的字符串集合的 BWT 的成本阻碍了这些技术广泛应用于 DNA 测序实验结果中经常遇到的大型序列集。在之前的工作中，我们提出了一种新颖的算法，允许在非常中等的硬件上计算人类基因组规模数据的 BWT，从而使我们能够研究 BWT 作为压缩此类数据集的工具。结果：我们首先使用模拟读取来探索压缩水平和错误率、读取长度和底层基因组采样水平之间的关系，并比较第二阶段的选择 我们证明，通过对集合中的序列进行特定的重新排序可以大大改善压缩，并给出一种新颖的“隐式排序”策略，该策略可以实现这些好处，而无需对读取进行排序的开销。通过这些技术，真实人类基因组序列数据的 45 倍覆盖率可无损压缩至每个碱基 0.5 位以下，从而使 135.3 Gb 的序列仅适合 8.2 GB 的空间（从读数中修剪一小部分低质量碱基，进一步提高压缩效果）。这比基于标准 BWT 的压缩器 () 在未修剪读数上实现的大小小 4 倍以上，但是 我们的方法的另一个重要优点是，它有助于在大规模 DNA 序列集合上构建压缩全文索引，例如 FM 索引。
Motivation: The Burrows-Wheeler transform (BWT) is the foundation of many algorithms for compression and indexing of text data, but the cost of computing the BWT of very large string collections has prevented these techniques from being widely applied to the large sets of sequences often encountered as the outcome of DNA sequencing experiments. In previous work, we presented a novel algorithm that allows the BWT of human genome scale data to be computed on very moderate hardware, thus enabling us to investigate the BWT as a tool for the compression of such datasets.Results: We first used simulated reads to explore the relationship between the level of compression and the error rate, the length of the reads and the level of sampling of the underlying genome and compare choices of second-stage compression algorithm.We demonstrate that compression may be greatly improved by a particular reordering of the sequences in the collection and give a novel 'implicit sorting' strategy that enables these benefits to be realized without the overhead of sorting the reads. With these techniques, a 45x coverage of real human genome sequence data compresses losslessly to under 0.5 bits per base, allowing the 135.3 Gb of sequence to fit into only 8.2 GB of space (trimming a small proportion of low-quality bases from the reads improves the compression still further).This is > 4 times smaller than the size achieved by a standard BWT-based compressor () on the untrimmed reads, but an important further advantage of our approach is that it facilitates the building of compressed full text indexes such as the FM-index on large-scale DNA sequence collections.