Automatic Identification of SARS Coronavirus using Compression-Complexity Measures

Karthi Balasubramanian; Nithin Nagaraj

The first attempt at using data compression for phylogenetic tree construction was by Grumbach et al. in [16] . They explored the idea of compressing a sequence S using a sequence Q, where the degree of compression obtained by doing so would be an indicator of the distance between them. Although their definition was not mathematically valid, it set a platform for researchers to explore in this area. Varre et al. [17] defined a transformation distance when sequence Q is transformed to sequence S by various mutations like segment-copy, segment-reverse copy and segment-insertion. Li et al. [18] define a relative distance measure by using a compression algorithm called GenCompress [19] that is based on approximate repeats in DNA sequences. Using the concept of Kolmogorov complexity, the compression algorithm has been used to propose a distance between sequences S and Q. But Kolmogorov complexity, [20] being an algorithmic measure of information and a theoretical limit, can't be directly computed but only approximately estimated [21] . Hence it is not an optimum choice as a complexity measure.