BioMed Central | Full text | Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment

BMC Bioinfomatics has an interesting article on alternatives to aligning sequences with genomic data.

BioMed Central Full text Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment

Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment.
Paolo Ferragina1 , Raffaele Giancarlo2 , Valentina Greco2 , Giovanni Manzini3 and Gabriel Valiente4

Background
Similarity of sequences is a key mathematical notion for Classification and Phylogenetic studies in Biology. It is currently primarily handled using alignments. However, the alignment methods seem inadequate for post-genomic studies since they do not scale well with data set size and they seem to be confined only to genomic and proteomic sequences. Therefore, alignment-free similarity measures are actively pursued. Among those, USM (Universal Similarity Metric) has gained prominence. It is based on the deep theory of Kolmogorov Complexity and universality is its most novel striking feature. Since it can only be approximated via data compression, USM is a methodology rather than a formula quantifying the similarity of two strings. Three approximations of USM are available, namely UCD (Universal Compression Dissimilarity), NCD (Normalized Compression Dissimilarity) and CD (Compression Dissimilarity). Their applicability and robustness is tested on various data sets yielding a first massive quantitative estimate that the USM methodology and its approximations are of value. Despite the rich theory developed around USM, its experimental assessment has limitations: only a few data compressors have been tested in conjunction with USM and mostly at a qualitative level, no comparison among UCD, NCD and CD is available and no comparison of USM with existing methods, both based on alignments and not, seems to be available.