点击次数：

所属单位：山东大学数学学院

发表刊物：SIAM Journal on Computing

关键字：approximation algorithms, computational molecular biology, distinguishing substring selection

摘要：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.,...

全部作者：Li, G.,Ma, B.

第一作者：Deng, X.

论文类型：期刊论文

通讯作者：Wang, L.

学科门类：理学

一级学科：数学

文献类型：J

卷号：32

期号：4

是否译文：否

发表时间：2003-06-01

收录刊物：SCI