A Generalized Hamming Distance of Sequence Patterns

2022/04/04 by Liu, Pengyu, Na, Jingzhou
#05A05 #40B99 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2204.01808

Abstract

We define sequence patterns of length n and level ℓ to be equivalence classes of sequences that have n elements from the set of ℓ integer symbols \1,2,…,ℓ\ with no restriction on repetition, where the equivalence relation is induced by symbol relabeling without swapping positions of symbols. We define a distance for a set of k sequence patterns of length n and level ℓ by generalizing the Hamming distance between sequences. We compute the maximal distance for k sequence patterns of length n and level ℓ and demonstrate how to calculate the exact distance between a pair of length-n level-ℓ sequence patterns.

Related

• Approximating Text-to-Pattern Distance via Dimensionality Reduction
• Matching Patterns with Variables under Hamming Distance
• Faster Approximate(d) Text-to-Pattern L1 Distance
• The sequence reconstruction problem for permutations with the Hamming distance
• Approximating Text-to-Pattern Hamming Distances