Generalized approximate regularities in strings

Abstract

We concentrate on generalized string regularities and study the minimum approximate λ-cover problem and the minimum approximate λ-seed problem of a string. Given a string x of length n and an integer λ, the minimum approximate λ-cover (respectively, seed) problem is to find a set of λ substrings each of equal length that covers x (respectively, a superstring of x) with the minimum error, under a variety of distance models containing the Hamming distance, the edit distance and the weighted edit distance. Both problems can be solved in polynomial time.

Keywords:

• Minimum λ-cover problem
• Minimum λ-seed problem
• λ-combinations
• Equivalence class
• Generalized approximate string regularities