Approximate Patterns in Strings
Ajay Chriscoe, and Liem Mai
The study of approximate patterns in strings has
important applications in molecular biology, information theory, and data
compression to name a few. In this paper, we study patterns such as covers and
seeds and their approximate versions built upon various commonly used distance
measures. We consider three related problems for both approximate covers and
approximate seeds, for two of which we derive polynomial-time algorithms, while
we show that the third problem is NP-complete. We also consider circular
string versions of these problems for approximate covers.
Keywords: String, approximate cover,
approximate seed, distance measure, string algorithms, dynamic programming.