Versatile string kernels

This paper proposes a class of string kernels that can handle a variety of subsequence-based features. Slight adaptations of the basic algorithm allow for weighing subsequence lengths, restricting or soft-penalizing gap-size, character-weighing and soft-matching of characters. An easy extension of the kernels allows for comparing run-length encoded strings with a time-complexity that is independent of the length of the original strings. Such kernels have applications in image processing, computational biology, in demography and in comparing partial rankings.

Authors

• Cees H. Elzinga
• Hui Wang Harbin Engineering University

Keywords

• String kernel
• String matching
• Subsequences
• Gap-penalizing
• Soft matching
• Run-length encoding
• Partial rankings