Data Compression Concepts and Algorithms and their Applications to Bioinformatics

Abstract

Data compression at its base is concerned with how information is organized in data. Understanding this organization can lead to efficient ways of representing the information and hence data compression. In this paper we review the ways in which ideas and approaches fundamental to the theory and practice of data compression have been used in the area of bioinformatics. We look at how basic theoretical ideas from data compression, such as the notions of entropy, mutual information, and complexity have been used for analyzing biological sequences in order to discover hidden patterns, infer phylogenetic relationships between organisms and study viral populations. Finally, we look at how inferred grammars for biological sequences have been used to uncover structure in biological sequences.

Figure 1

Plot of the redundancy rate versus $\frac{D_2}{D_1+D_2}$ using the genes available at the time shows a clear segregation of Phage, Bacteria, and Vertebrate sequences.

Figure 2

Inclusion of additional sequences breaks down the segregation observed by Gatlin.

Figure 3

The logo of a number of sequences at the beginning of a gene. The start codon ATG is immediately apparent. The logo was constructed using the software at http://weblogo.threeplusone.com/.

Figure 4

AMI charts for HIV-1 populations isolated from patients who remained asymptomatic. The large number of white pixels indicate generally a high degree of covariation while “checkerboard” regions indicate specific segments of the envelope protein with correlated mutations [20].

Figure 5

AMI charts for HIV-1 populations isolated from patients who succumbed to AIDS. The preponderance of black pixels indicates a relatively homogeneous population [20].

Figure 6

A block diagram depicting the basic steps involved with a grammar-based compression scheme.