CHAPAO: Likelihood and hierarchical reference-based representation of biomolecular sequences and applications to compressing multiple sequence alignments

Abstract

Background: High-throughput experimental technologies are generating tremendous amounts of genomic data, offering valuable resources to answer important questions and extract biological insights. Storing this sheer amount of genomic data has become a major concern in bioinformatics. General purpose compression techniques (e.g. gzip, bzip2, 7-zip) are being widely used due to their pervasiveness and relatively good speed. However, they are not customized for genomic data and may fail to leverage special characteristics and redundancy of the biomolecular sequences.

Results: We present a new lossless compression method CHAPAO (COmpressing Alignments using Hierarchical and Probabilistic Approach), which is especially designed for multiple sequence alignments (MSAs) of biomolecular data and offers very good compression gain. We have introduced a novel hierarchical referencing technique to represent biomolecular sequences which combines likelihood based analyses of the sequence similarities and graph theoretic algorithms. We performed an extensive evaluation study using a collection of real biological data from the avian phylogenomics project, 1000 plants project (1KP), and 16S and 23S rRNA datasets. We report the performance of CHAPAO in comparison with general purpose compression techniques as well as with MFCompress and Nucleotide Archival Format (NAF)-two of the best known methods especially designed for FASTA files. Experimental results suggest that CHAPAO offers significant improvements in compression gain over most other alternative methods. CHAPAO is freely available as an open source software at https://github.com/ashiq24/CHAPAO.

Conclusion: CHAPAO advances the state-of-the-art in compression algorithms and represents a potential alternative to the general purpose compression techniques as well as to the existing specialized compression techniques for biomolecular sequences.

Fig 1. Character evolution and multiple sequence alignment.

(a) Two observed sequences, (b) Character evolution with substitution and indels which can change the sequence length and blur the homology, and (c) Multiple sequence alignment of the two sequences capturing the underlying character evolution where each site consists of homologous characters.

Fig 2. Overview of the compression and decompression techniques in CHAPAO.

A directed weighted “Encodability Graph” is constructed where each vertex corresponds to a sequence in MSA except for the dummy node (shown in red) which is used as a “source” vertex. Next, a minimum spanning arborescence $\mathcal{M}\mathcal{A}$ in the graph is constructed. Sequences that are children of the dummy node in the $\mathcal{M}\mathcal{A}$ will be used as reference sequences. Appropriate metadata are generated to hierarchically represent all other sequences. Finally, the reference sequences along with the metadata are compressed using existing compression techniques. The pipeline is completely reversible, allowing lossless decompression of the original MSAs.

Fig 3. Directed graph based modeling.

(a) A multiple sequence alignment with three sequences, (b) the corresponding cost matrix, (c) the encodability graph $\mathcal{E}\mathcal{G}$, and (d) the corresponding minimum spanning arborescence $\mathcal{M}\mathcal{A}$.

Fig 4. Performance of various compression techniques on avian datasets.

To better understand the relative performance of different methods across different file sizes, we distribute the MSA files into various bins based on their sizes. For each bin (file-size range), we show the average size of the compressed files produced by various methods. (a) UCEs. (b) Introns. (c) Exons.

Fig 5. Performance of various compression techniques on 10 concatenated alignments in avian dataset.

Fig 6. Performance of CHAPAO with varying levels of dissimilarity/divergence of the 14,490 MSAs in avian datasets.

The average hamming distance (as defined in Eq 4) of these files ranges from 0–13. The box plots show the compression ratio (ratio of the size of the original file and the compressed file) of CHAPAO on the MSAs in avian datasets (here MSAs are sorted in an ascending order of their average hamming distance).

Fig 7. Comparison of various compression techniques on 16S and 23S datasets and 1KP dataset.

(a) 16S. (b) 23S. (c) 1KP.

Fig 8. Impact of the lengths of sliding window and overlap on compression ratio.

We show the performance of various variants of CHAPAO on 16S and 23S datasets. (a) 16S. (b) 23S.