A PTAS for distinguishing (sub)string selection

Consider two sets of strings, B (badgenes) and G (good genes), as well as two integers d_b and d_g (d_b ≤ d_g). A frequently occurring problem in computational biology (andother fields) is to finda (distinguishing) substring s of length L that distinguishes the bad strings from goodstrings, i.e., for each string s_i ∈ B there exists a length-L substring t_i of s_i with d(s, t _i) ≤ d_b (close to badstrings) andfor every substring u_i of length L of every string g_i ∈ G, d(s, u _i) ≤ d_g (far from goodstrings). We present a polynomial time approximation scheme to settle the problem, i.e., for any constant ε > 0, the algorithm finds a string s of length L such that for every s _i ∈ B, there is a length-L substring t_i of s _i with d(t_i, s) ≤ (1+ε)d_b andfor every substring ui of length L of every g_i ∈ G, d(u_i, s) ≤ (1 - ε)d_g, if a solution to the original pair (d _b ≤ d_g) exists. © 2002 Springer-Verlag Berlin Heidelberg.