TY - GEN
T1 - A Three-String Approach to the Closest String Problem
AU - Chen, Zhi-Zhong
AU - Ma, Bin
AU - Wang, Lusheng
PY - 2010/7
Y1 - 2010/7
N2 - Given a set of n strings of length L and a radius d, the closest string problem asks for a new string t sol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in time, while the previous best runs in O (nL + nd3 6.731d)
time, while the previous best runs in O (nL + nd8d) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in O (nL + nd1.612d (α2 + 1 − 2α−1 + α−2)3d) time, where α = 3√ √|Σ| − 1 + 1. This new time bound is better than the previous best for small alphabets, including the very important case where |∑|=4 (i.e., the case of DNA strings).
AB - Given a set of n strings of length L and a radius d, the closest string problem asks for a new string t sol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in time, while the previous best runs in O (nL + nd3 6.731d)
time, while the previous best runs in O (nL + nd8d) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in O (nL + nd1.612d (α2 + 1 − 2α−1 + α−2)3d) time, where α = 3√ √|Σ| − 1 + 1. This new time bound is better than the previous best for small alphabets, including the very important case where |∑|=4 (i.e., the case of DNA strings).
UR - http://www.scopus.com/inward/record.url?scp=77955020000&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-77955020000&origin=recordpage
U2 - 10.1007/978-3-642-14031-0_48
DO - 10.1007/978-3-642-14031-0_48
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3642140300
SN - 9783642140303
T3 - Lecture Notes in Computer Science
SP - 449
EP - 458
BT - Computing and Combinatorics
A2 - Thai, My T.
A2 - Sahni, Sartaj
T2 - 16th Annual International Computing and Combinatorics Conference (COCOON 2010)
Y2 - 19 July 2010 through 21 July 2010
ER -