Clustering the Normalized Compression Distance for Influenza Virus Data

Authors: Kimihito Ito, Thomas Zeugmann¹, and Yu Zhu

Source: Algorithms and Applications, Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday , (Tapio Elomaa, Heikki Mannila, and Pekka Orponen, Eds.), Lecture Notes in Computer Science 6060, pp. 130 - 146, Springer 2010.

Abstract. The present paper analyzes the usefulness of the normalized compression distance for the problem to cluster the hemagglutinin (HA) sequences of influenza virus data for the HA gene in dependence on the available compressors. Using the CompLearn Toolkit, the built-in compressors zlib and bzip2 are compared. Moreover, a comparison is made with respect to hierarchical and spectral clustering. For the hierarchical clustering, hclust from the R package is used, and the spectral clustering is done via the kLine algorithm proposed by Fischer and Poland (2004). Our results are very promising and show that one can obtain an (almost) perfect clustering. It turned out that the zlib compressor allowed for better results than the bzip2 compressor and, if all data are concerned, then hierarchical clustering is a bit better than spectral clustering via kLines.