GTRAC: fast retrieval from compressed collections of genomic variants

Abstract

Motivation: 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.

Results: 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.

Availability and implementation: The GTRAC algorithm is available for download at: https://github.com/kedartatwawadi/GTRAC CONTACT: : kedart@stanford.edu

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

GTRAC allows for fast access of information of a specific variant or the genotype of a sample/group of samples over the compressed VCF file

Fig. 2.

Example of a binary matrix $\mathcal{H}$ representing the presence/absence of variants in the haplotypes. Note that in this representation, columns represent variant information across samples and rows represent haplotypes of a given sample

Fig. 3.

A simple example of the parsing process. The $3\times 20matrix\mathcal{H}$ is first converted to the $3\times 10$ symbol matrix ${\mathcal{H}}_2$ ($K=2$). Then the parsing is performed sequentially at each row (starting on the first row), from left to right

Fig. 4.

A simple example of rank and select usage corresponding to the phraseEnd vectors of example of Figure 3

Fig. 5.

The recursive algorithm for sub-string extraction from the compressed symbol matrix ${\mathcal{H}}_K$. The input parameters $(vid,start,len)$ correspond to the row-id, the start position, and the length, respectively, of the sub-string we want to extract

Fig. 6.

The Recursive Algorithm for extraction of a specific variant with column-id $cid$, from all the rows