Traditional methods for comparing sequences often fall into two extremes. "Bag-of-words" models ignore order entirely, treating a document or a DNA strand as an unordered collection of tokens. Conversely, global alignment methods like the Edit Distance or Smith-Waterman algorithm look for a single optimal way to line up two sequences.
Local alignment and string kernels offer a middle ground. They measure similarity by decomposing sequences into their constituent substructures—such as subsequences, substrings, or motifs—and counting how many of these parts they share. This approach allows models to capture the structural "shape" of data without requiring rigid, perfect matches.
The Intuition of Subsequence Matching
The core challenge in sequence analysis is handling "noise" or insertions. In natural language, two sentences might express the same relationship even if one contains extra adjectives. In biology, two proteins might share a functional motif despite having different amino acids in between.
Lodhi et al. addressed this by proposing the String Subsequence Kernel (SSK). Instead of looking for exact word matches, the kernel maps text into a high-dimensional space where every possible character subsequence of a fixed length is a feature. Crucially, these subsequences do not have to be contiguous. For example, the word "kernel" contains the subsequence "k-r-l".
To prevent the model from finding meaning in purely random coincidences, the authors introduced a decay parameter. This parameter penalizes matches that are spread across a large span of the original text. A compact match like "cat" in "the cat" is weighted more heavily than a fragmented match like "c...a...t" in "the car is at the top." This mechanism, also utilized by Bunescu et al. for relation extraction, ensures that local structural proximity is prioritized over distant, sparse patterns.
From Best Alignment to All Alignments
In bioinformatics, researchers often look for the "best" local alignment between two sequences to determine similarity. However, Salomon et al. argue that this ignores a wealth of information. A single optimal alignment might miss subtle, secondary patterns that also indicate a shared biological function.
The Local Alignment Kernel solves this by summing the scores of all possible local alignments between two sequences. By considering the entire ensemble of potential matches rather than just the winner, the model becomes more robust to variations in sequence length and composition. This approach has proven particularly effective in predicting how peptides bind to MHC molecules, where flexible binding configurations are common.
Capturing Position and Context
Not all matches are created equal. In many structured sequences, where a match occurs is just as important as what matches.
- Weighted Degrees: Sonnenburg et al. introduced the Weighted Degree Kernel for DNA splice site prediction. This method counts matching substrings at identical positions across two sequences but assigns higher weights to longer matches. This captures local dependencies—the idea that a specific sequence of nucleotides is more significant than the sum of its individual parts.
- Position Sensitivity: As Ben-Hur et al. explain, position-sensitive kernels evaluate similarity by matching identical substrings only if they occur at the same relative offsets. This is vital for identifying biological signals, such as promoter regions, which are functionally tied to their distance from a gene.
Beyond Text and Biology
While these kernels originated in NLP and bioinformatics, their ability to handle discrete, ordered data makes them versatile. Grosnit et al. applied string kernels to logic synthesis, using them to navigate the search space of circuit optimizations. By identifying shared sequences of operations, the kernel allows a Bayesian Optimization framework to understand which sequences of logic gates are likely to produce efficient hardware.
Similarly, Huang et al. and Duan et al. demonstrated that borrowing dynamic programming algorithms from bioinformatics allows for the extraction of "flexible" multi-word expressions in language, such as "make a decision," which can be interrupted by various modifiers.
By treating sequences as collections of weighted, overlapping, and potentially gapped substructures, local alignment kernels provide a mathematically rigorous way to compare complex data that traditional distance metrics simply cannot see.
Key Foundational Work
Text Classification using String Kernels (2000) — contributed 2 concept elements to this direction.
Text Classification using String Kernels (2002) — contributed 1 concept elements to this direction.