Institution:山东大学数学学院

Title of Paper:Genetic Design of Drugs without Side-effects

Journal:SIAM Journal on Computing

Key Words:approximation algorithms, computational molecular biology, distinguishing substring selection

Summary: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.,...

First Author:Deng, X.

Correspondence Author:Wang, L.

All the Authors:Li, G.,Ma, B.

Indexed by:Journal paper

Discipline:Natural Science

First-Level Discipline:Mathematics

Document Type:J

Volume:32

Issue:4

Translation or Not:No

Date of Publication:2003-06

Included Journals:SCI

Release Time:2019-07-10