GVC: efficient random access compression for gene sequence variations

Abstract

Background: In recent years, advances in high-throughput sequencing technologies have enabled the use of genomic information in many fields, such as precision medicine, oncology, and food quality control. The amount of genomic data being generated is growing rapidly and is expected to soon surpass the amount of video data. The majority of sequencing experiments, such as genome-wide association studies, have the goal of identifying variations in the gene sequence to better understand phenotypic variations. We present a novel approach for compressing gene sequence variations with random access capability: the Genomic Variant Codec (GVC). We use techniques such as binarization, joint row- and column-wise sorting of blocks of variations, as well as the image compression standard JBIG for efficient entropy coding.

Results: Our results show that GVC provides the best trade-off between compression and random access compared to the state of the art: it reduces the genotype information size from 758 GiB down to 890 MiB on the publicly available 1000 Genomes Project (phase 3) data, which is 21% less than the state of the art in random-access capable methods.

Conclusions: By providing the best results in terms of combined random access and compression, GVC facilitates the efficient storage of large collections of gene sequence variations. In particular, the random access capability of GVC enables seamless remote data access and application integration. The software is open source and available at https://github.com/sXperfect/gvc/ .

Keywords: Compression; Random access; VCF; Variants.

Fig. 1

Block diagram of the proposed encoding process. The genotype matrix $\mathcal{G}$ is processed by a series of transformations: splitting, binarization, and optionally sorting. At the end of the process, entropy coding is applied

Fig. 2

Example for $\mathcal{G}=\begin{array}{cc}0\mid 2\hfill & 2/0\hfill \\ 1/0\hfill & 0\mid 0\hfill \end{array}$. Bit plane binarization yields two bit planes representing the most significant bit and the less significant bit of $\mathcal{A}$. Row binarization generates only three binary rows because the first row of $\mathcal{A}$ requires two bits and the second row of $\mathcal{A}$ requires only one bit

Fig. 3

Average compression ratio (averaged over all chromosomes) achieved by each GVC configuration. The colors indicate the employed binarization: orange—bit plane binarization (concatenated), blue—bit plane binarization, green—row binarization. The patterns indicate the employed sorting: no pattern—no sorting, vertical lines—column sorting, horizontal lines—row sorting, both horizontal and vertical lines—sorting in both directions

Fig. 4

Compression ratio achieved by each GVC configuration with different block sizes. For all configurations with the sorting enabled, increasing the block size increases the compression ratio

Fig. 5

Comparison of GVC to the state-of-the-art methods GTC [4], GTRAC [3], and GTShark [5] with respect to compressed size

Fig. 6

Comparison of random access time between GTC [4] and GVC with respect to the range size

Fig. 7

Comparison of random access time between GTC [4] and GVC with respect to the number of samples

Fig. 8

An example of a random access process on compressed genotypes where the number of alternate alleles is one and the blocks are transformed using bit plane binarization and sorted in row direction. A user needs the genotypes of all samples on chromosome 2 at loci 1000 through 1100, represented by “chr2:1000-1100”. First, GVC finds the blocks containing the required genotype information using a block lookup process. The bitstreams of the selected block, in this case the block with ID 1, are then decoded, yielding the sort indices $\tilde{a}$ and the binary matrix $\mathcal{B}$. Using the position information of each variant site, GVC selects certain rows or columns of the binary matrix $\mathcal{B}$ and based on the sort index $\tilde{a}$. Finally, the selected rows and columns of the binary matrix $\mathcal{B}$ are then inverse transformed to return the genotypes of all samples at loci 1000 through 1100