Tatwawadi Kedar, Hernaez Mikel, Ochoa Idoia, Weissman Tsachy
Department of Electrical Engineering, Stanford University, 350 Serra Mall, Stanford, CA, USA.
Bioinformatics. 2016 Sep 1;32(17):i479-i486. doi: 10.1093/bioinformatics/btw437.
The dramatic decrease in the cost of sequencing has resulted in the generation of huge amounts of genomic data, as evidenced by projects such as the UK10K and the Million Veteran Project, with the number of sequenced genomes ranging in the order of 10 K to 1 M. Due to the large redundancies among genomic sequences of individuals from the same species, most of the medical research deals with the variants in the sequences as compared with a reference sequence, rather than with the complete genomic sequences. Consequently, millions of genomes represented as variants are stored in databases. These databases are constantly updated and queried to extract information such as the common variants among individuals or groups of individuals. Previous algorithms for compression of this type of databases lack efficient random access capabilities, rendering querying the database for particular variants and/or individuals extremely inefficient, to the point where compression is often relinquished altogether.
We present a new algorithm for this task, called GTRAC, that achieves significant compression ratios while allowing fast random access over the compressed database. For example, GTRAC is able to compress a Homo sapiens dataset containing 1092 samples in 1.1 GB (compression ratio of 160), while allowing for decompression of specific samples in less than a second and decompression of specific variants in 17 ms. GTRAC uses and adapts techniques from information theory, such as a specialized Lempel-Ziv compressor, and tailored succinct data structures.
The GTRAC algorithm is available for download at: https://github.com/kedartatwawadi/GTRAC CONTACT: : kedart@stanford.edu
Supplementary data are available at Bioinformatics online.
测序成本的大幅下降导致了大量基因组数据的产生，英国10K计划和百万退伍军人计划等项目便是例证，测序基因组的数量在1万到100万的量级。由于同一物种个体的基因组序列存在大量冗余，大多数医学研究处理的是与参考序列相比的序列变异，而非完整的基因组序列。因此，数以百万计表示为变异的基因组被存储在数据库中。这些数据库不断更新和查询，以提取个体或个体群体中的常见变异等信息。以前用于压缩此类数据库的算法缺乏有效的随机访问能力，使得查询数据库中特定的变异和/或个体极其低效，以至于压缩常常被完全放弃。
我们提出了一种用于此任务的新算法，称为GTRAC，它在实现显著压缩率的同时，允许对压缩数据库进行快速随机访问。例如，GTRAC能够将包含1092个样本的智人数据集压缩到1.1GB（压缩率为160），同时允许在不到一秒的时间内解压缩特定样本，并在17毫秒内解压缩特定变异。GTRAC使用并改编了信息论中的技术，如专门的Lempel-Ziv压缩器和定制的简洁数据结构。
GTRAC算法可在以下网址下载：https://github.com/kedartatwawadi/GTRAC 联系方式：kedart@stanford.edu
补充数据可在《生物信息学》在线获取。
