LZW-Kernel

LZW-Kernel implements a convolutional kernel that compares protein sequences using variable-length code words from the Lempel-Ziv-Welch (LZW) compressor to provide an alignment-free similarity measure for classification and remote homology detection.

Key Features:

• Alignment-Free Methodology: Uses variable-length code blocks derived from the Lempel-Ziv-Welch (LZW) universal text compressor to compare protein sequences without sequence alignments.
• Symmetric and Positive Kernel Function: Defines a kernel that is symmetric and positive and yields a self-similarity score of 1.0.
• Direct SVM Compatibility: Integrates directly with Support Vector Machines (SVMs) without requiring additional normalization techniques used for the normalized compression distance.
• One-Pass Efficiency and Speed: Operates as a one-pass algorithm suitable for big data and is reported to be approximately three times faster than BLAST and orders of magnitude faster than Smith-Waterman (SW) or the Local Alignment Kernel (LAK).
• Comparable or Superior Performance: Demonstrates performance close to the Local Alignment Kernel (LAK) and SVM-pairwise with Smith-Waterman scoring and outperforms SVM-pairwise approaches using BLAST scores in remote protein homology detection and classification.

Scientific Applications:

• Remote Protein Homology Detection: Applied to detect distant evolutionary relationships between protein sequences without alignments.
• Protein Sequence Classification: Used as a kernel source for SVM-based classification of protein sequences.
• Large-Scale Alignment-Free Sequence Analysis: Suited for high-throughput, big data comparison of protein sequences where computational efficiency is required.

Methodology:

Maps protein sequences to variable-length LZW code words via one-pass Lempel-Ziv-Welch compression and computes a symmetric, positive convolutional kernel from those code words to produce similarity scores compatible with SVMs.