GENETIC DESIGN OF DRUGS WITHOUT SIDE-EFFECTS.

Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ≤ dg). 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 si Ε B there exists a length-L substring ti of si with d(s, ti) ≤ db (close to bad strings), and for every substring ui of length L of every string gi Ε G, d(s, ui) ≥ dg (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 si Ε B there is a length-L substring ti of si with d(ti, s) ≤ ( 1 + ε)db, and for every substring ui of length L of every gi ε G, d(ui, s) ≥ (1 − ε)dg if a solution to the original pair (db ≤ dg) exists. Since there is a polynomial number of such pairs (db, dg), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems. [ABSTRACT FROM AUTHOR]