Word Motifs and a Generalized Hamming Distance

Abstract

Combinatorics on words is a relatively recent and rich field that involves formal grammar, algebra, geometry, fractals, algorithms, and coding, with initial research focused on repetitions in words. In this paper, we measure the differences between patterns shared by words of the same length. We introduce word motifs to represent collections of words that share the same underlying patterns, and we generalize the Hamming distance for comparing word motifs. A word motif is an equivalence class of words of the same length over an alphabet under the equivalence relation induced by symbol relabeling. We study initial problems in comparing word motifs. We compute the maximal generalized Hamming distance for k word motifs of length n over an alphabet of ℓ symbols, and we demonstrate how to calculate the exact generalized Hamming distance between a pair of word motifs.