A MORE EFFICIENT CLOSEST STRING ALGORITHM

摘要

In this paper, we study the closest string problem. This problem has applications in universal PCR primer design, genetic probes design, motif finding, and an-tisense drug design, etc. Because of its wide applications, this problem has been extensively studied in recent years.rnThe problem is defined as follows: given a set of strings S = {s_1, s_2, ..., s_n}, each of length L, the objective is to construct a center string s of length L such that the radius max_1≤1≤n d(s, s_i) is minimized, where d(.,.) is the Hamming distance. Although this problem is a NP-complete problem, researchers have developed fixed-parameter algorithms to tackle this problem. When the radius d is the parameter, the best-known fixed-parameter algorithm [21] for the closest string has time complexity O(Ln+nd(|Σ|-1)~d 2~(3.25d)), where |E| is the size of the alphabet.rnWe improved the algorithm proposed in [14]. The time complexity of our algorithm is O(Ln + nd · (2|Σ| + 4(|Σ| - 1))~(1/2)~d) which is better than the best known algorithm.