Space-efficient whole genome comparisons with Burrows-Wheeler transforms
Space-efficient whole genome comparisons with Burrows-Wheeler transforms
复制标题
DOI：
10.1089/cmb.2005.12.407
复制
发表时间：
2005-05-01
影响因子：
1.7
通讯作者：
Lippert, RA
中科院分区：
文献类型：
--
作者：
Lippert, RA
哺乳动物基因组任何比对的起点是计算满足各种标准的精确匹配。用于这种计算的时间高效的O(n)数据结构，比如后缀树，需要O(n log(n))的空间，是基因组自身空间的数倍。因此，任何合理的全基因组比较项目都会发现自身需要几十吉字节的随机存取存储器（RAM）来保持时间效率。这超出了大多数现代工作站的能力。通过一种新的数据结构，即通过Burrows - Wheeler变换实现的压缩后缀数组（CSA），我们可以用时间效率来换取空间效率，耗费O(n log(n))的时间，但在O(n)空间中运行，通常总空间小于或等于基因组自身的空间。如果空间比时间更昂贵，这是一种值得考虑的合适方法。这种数据结构最节省空间的实现方式在最坏情况下，每个核苷酸字符需要5比特来在线构建，构建完成后每个字符需要2.5比特来存储。我们介绍了这种数据结构以及它如何用于获取匹配。通过在一台配备不到2GB可用随机存取存储器的普通工作站上比对两个哺乳动物基因组，一种实现（称为bbbwt）在时间上优于其他数据结构的实现，从而得到了验证。
The starting point for any alignment of mammalian genomes is the computation of exact matches satisfying various criteria. Time- efficient, O( n), data structures for this computation, such as the suffix tree, require O( n log( n)) space, several times the space of the genomes themselves. Thus, any reasonable whole- genome comparative project finds itself requiring tens of Gigabytes of RAM to maintain time- efficiency. This is beyond most modern workstations. With a new data structure, the compressed suffix array ( CSA) implemented via the Burrows - Wheeler transform, we can trade time- efficiency for space- efficiency, taking O( n log( n)) time, but running in O( n) space, typically in total space less than or equal to that of the genomes themselves. If space is more expensive than time, this is an appropriate approach to consider. The most space- efficient implementation of this data structure requires 5 bits per nucleotide character to build on- line, in the worst case, and 2.5 bits per character to store once built. We present a description of this data structure and how it is used to obtain matches. An implementation ( called bbbwt) is demonstrated by aligning two mammalian genomes on a modest workstation equipped with under 2 GB of free RAM in time superior to that of the implementations of other data structures.