Affiliation of Author(s):山东大学数学学院

Journal:SIAM Journal on Computing

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

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

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

First Author:Deng, X.

Indexed by:Journal paper

Correspondence Author:Wang, L.

Discipline:Natural Science

First-Level Discipline:Mathematics

Document Type:J

Volume:32

Issue:4

Translation or Not:no

Date of Publication:2003-06-01

Included Journals:SCI