Randomized and Parameterized Algorithms for the Closest String Problem
Randomized and Parameterized Algorithms for the Closest String Problem
复制标题
DOI：
10.1007/978-3-319-07566-2_11
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Zhi-Zhong Chen;Bin Ma;Lusheng Wang
中科院分区：
文献类型：
--
作者：
Zhi-Zhong Chen;Bin Ma;Lusheng Wang
给定一个等长L的字符串集合S={s1，s2，...，sn}和一个整数d，最近串问题（CSP）要求计算长度为L的字符串s，使得对于每个si∈ S，d（s，si）≤ d，其中d（s，si）是s和si之间的汉明距离。该问题是NP-困难的，并已被广泛研究的近似算法和参数化算法的上下文中。参数化算法为生物信息学中的实际应用提供了最实用的解决方案。在本文中，我们开发的第一个随机参数化算法CSP。随机算法不仅比确定性算法简单得多，而且它们的预期时间复杂度也明显优于以前最知名的（确定性）算法。
Given a set S={s 1, s 2,…, sn} of strings of equal length L and an integer d, the closest string problem (CSP) requires the computation of a string s of length L such that d (s, si)≤ d for each si∈ S, where d (s, si) is the Hamming distance between s and si. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and parameterized algorithms. Parameterized algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized parameterized algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their expected-time complexities are also significantly better than the previously best known (deterministic) algorithms.