Learning String Kernels Utilizing Adaptive Variable Length Compression

Currently there exists many approaches to classifying protein strings in bioinformatics and one of these approaches is based on string-specific distance/similarity measures. In this thesis a new convolutional kernel over strings is presented – the LZW-kernel, which is based on Lempel-Ziv-Welch compression algorithm. The motivation for a novel method is that there exists a tradeoff between computational complexity of the algorithm, which determines distance/similarity between strings and its further quality, as a measure applied to various machine learning algorithms. Our goal is to reduce this gap – utilizing an algorithm less computationally intensive, than current leader (which is Smith-Waterman alignment score). LZW-kernel was tested with two classification algorithms – SVM and k-NN with various number of neighbors. We managed to get better classification quality than any of quadratic time string comparison methods, but not surpassing the classification quality of a leader, which is cubic in time.