Distinguishing string selection problems. Lanctot, J. K., Li, M., Ma, B., Wang, S., & Zhang, L. Inform Comput, 185(1):41–55, 2003. ![Distinguishing string selection problems [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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 -approximation algorithm for the Closest String Problem for any small constant [epsilon]>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[epsilon] in polynomial time for some fixed constant [epsilon] unless NP=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.
@Article{lanctot03distinguishing,
author = {J. Kevin Lanctot and Ming Li and Bin Ma and Shaojiu Wang and Louxin Zhang},
title = {Distinguishing string selection problems},
journal = {Inform Comput},
year = {2003},
volume = {185},
number = {1},
pages = {41--55},
issn = {0890-5401},
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 -approximation algorithm for the Closest String Problem for any small constant [epsilon]>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[epsilon] in polynomial time for some fixed constant [epsilon] unless NP=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.},
doi = {10.1016/S0890-5401(03)00057-9},
keywords = {center string, gene clusters},
owner = {Sebastian},
timestamp = {2010.04.19},
url = {http://www.sciencedirect.com/science/article/B6WGK-48D37KJ-3/2/219c09ad466c21ba5d31e8f20793ce48},
}
Downloads: 0
{"_id":"PgKz9uetyAZwTTGz4","bibbaseid":"lanctot-li-ma-wang-zhang-distinguishingstringselectionproblems-2003","downloads":0,"creationDate":"2018-03-26T07:07:40.720Z","title":"Distinguishing string selection problems","author_short":["Lanctot, J. K.","Li, M.","Ma, B.","Wang, S.","Zhang, L."],"year":2003,"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["J.","Kevin"],"propositions":[],"lastnames":["Lanctot"],"suffixes":[]},{"firstnames":["Ming"],"propositions":[],"lastnames":["Li"],"suffixes":[]},{"firstnames":["Bin"],"propositions":[],"lastnames":["Ma"],"suffixes":[]},{"firstnames":["Shaojiu"],"propositions":[],"lastnames":["Wang"],"suffixes":[]},{"firstnames":["Louxin"],"propositions":[],"lastnames":["Zhang"],"suffixes":[]}],"title":"Distinguishing string selection problems","journal":"Inform Comput","year":"2003","volume":"185","number":"1","pages":"41–55","issn":"0890-5401","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 -approximation algorithm for the Closest String Problem for any small constant [epsilon]>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[epsilon] in polynomial time for some fixed constant [epsilon] unless NP=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.","doi":"10.1016/S0890-5401(03)00057-9","keywords":"center string, gene clusters","owner":"Sebastian","timestamp":"2010.04.19","url":"http://www.sciencedirect.com/science/article/B6WGK-48D37KJ-3/2/219c09ad466c21ba5d31e8f20793ce48","bibtex":"@Article{lanctot03distinguishing,\n author = {J. Kevin Lanctot and Ming Li and Bin Ma and Shaojiu Wang and Louxin Zhang},\n title = {Distinguishing string selection problems},\n journal = {Inform Comput},\n year = {2003},\n volume = {185},\n number = {1},\n pages = {41--55},\n issn = {0890-5401},\n 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 -approximation algorithm for the Closest String Problem for any small constant [epsilon]>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[epsilon] in polynomial time for some fixed constant [epsilon] unless NP=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.},\n doi = {10.1016/S0890-5401(03)00057-9},\n keywords = {center string, gene clusters},\n owner = {Sebastian},\n timestamp = {2010.04.19},\n url = {http://www.sciencedirect.com/science/article/B6WGK-48D37KJ-3/2/219c09ad466c21ba5d31e8f20793ce48},\n}\n\n","author_short":["Lanctot, J. K.","Li, M.","Ma, B.","Wang, S.","Zhang, L."],"key":"lanctot03distinguishing","id":"lanctot03distinguishing","bibbaseid":"lanctot-li-ma-wang-zhang-distinguishingstringselectionproblems-2003","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6WGK-48D37KJ-3/2/219c09ad466c21ba5d31e8f20793ce48"},"keyword":["center string","gene clusters"],"metadata":{"authorlinks":{}}},"search_terms":["distinguishing","string","selection","problems","lanctot","li","ma","wang","zhang"],"keywords":["center string","gene clusters"],"authorIDs":[],"dataSources":["C5FtkvWWggFfMJTFX"]}