Genetic design of drugs without side-effects

Consider two sets of strings, ℬ (bad genes) and script G sign (good genes), as well as two integers d_b and d_g (d_b ≤ d_g). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string s_i ∈ ℬ there exists a length-L substring t _i of s_i with d(s, t_i) ≤ d_b (close to bad strings), and for every substring u_i of length L of every string g_i ∈ script G sign, d(s, u_i) ≥ d _g (far from good strings). 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 ∈ ℬ there is a length-L substring t_i of s_i with d(t_i, s) ≤ (1 + ε)d_b, and for every substring u_i of length L of every g_i ∈ script G sign, d(u _i, s) ≥ (1 - ε)d_g if a solution to the original pair (d_b ≤ d_g) exists. Since there is a polynomial number of such pairs (d_b, d_g), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems.