Please use this identifier to cite or link to this item:
Title: Distinguishing string selection problems
Authors: Lanctot, J.K.
Li, M.
Ma, B.
Wang, S.
Zhang, L. 
Issue Date: 25-Aug-2003
Citation: Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L. (2003-08-25). Distinguishing string selection problems. Information and Computation 185 (1) : 41-55. ScholarBank@NUS Repository.
Abstract: This paper presents a collection of string algorithms that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, universal primers or unbiased consensus sequences. All these problems reduce to the task of finding a pattern that, with some error, occurs in one set of strings (Closest Substring Problem) and does not occur in another set (Farthest String Problem). In this paper, we break down the problem into several subproblems and prove the following results. 1. The following are all NP-Hard: the Farthest String Problem, the Closest Substring Problem, and the Closest String Problem of finding a string that is close to each string in a set. 2. There is a PTAS for the Farthest String Problem based on a linear programming relaxation technique. 3. There is a polynomial-time (4/3 + ε)-approximation algorithm for the Closest String Problem for any small constant ε > 0. Using this algorithm, we also provide an efficient heuristic algorithm for the Closest Substring Problem. 4. The problem of finding a string that is at least Hamming distance d from as many strings in a set as possible, cannot be approximated within nε in polynomial time for some fixed constant ε unless N P = P, where n is the number of strings in the set. 5. There is a polynomial-time 2-approximation for finding a string that is both the Closest Substring to one set, and the Farthest String from another set.
Source Title: Information and Computation
ISSN: 08905401
DOI: 10.1016/S0890-5401(03)00057-9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 12, 2019


checked on Feb 4, 2019

Page view(s)

checked on Feb 8, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.