TY - JOUR
T1 - Designing and implementing algorithms for the closest string problem
AU - Yuasa, Shota
AU - Chen, Zhi-Zhong
AU - Ma, Bin
AU - Wang, Lusheng
PY - 2019/9
Y1 - 2019/9
N2 - Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string tsol 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). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n2L + n2d⋅6.16d) time, while the previously best deterministic algorithm runs in O (nL + nd3⋅6.731d) time.
AB - Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string tsol 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). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n2L + n2d⋅6.16d) time, while the previously best deterministic algorithm runs in O (nL + nd3⋅6.731d) time.
KW - Algorithm engineering
KW - Computational biology
KW - Fixed-parameter algorithms
KW - The closest string problem
UR - http://www.scopus.com/inward/record.url?scp=85047735648&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85047735648&origin=recordpage
U2 - 10.1016/j.tcs.2018.05.017
DO - 10.1016/j.tcs.2018.05.017
M3 - RGC 21 - Publication in refereed journal
VL - 786
SP - 32
EP - 43
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -