Please use this identifier to cite or link to this item:
|Title:||Distinguishing string selection problems|
|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. https://doi.org/10.1016/S0890-5401(03)00057-9|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 17, 2018
WEB OF SCIENCETM
checked on May 9, 2018
checked on May 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.