Approximate Patterns in Strings

P. Agius, F. Blanchet-Sadri, 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.