Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

摘要

In the paper, we study three related problems, the closest string problem, the farthest string problem and the distinguishing string selection problem. These problems have applications in motif detection, binding sites locating, genetic drug target identification, genetic probes design, universal PCR primer design, etc. They have been extensively studied in recent years.rnThe problems are defined as follows:rnThe closest string problem: given a group of strings B = {s_1, s_2, ..., s_n}, each of length L, and an integer d, the problem is to compute a center string s of length L such that the Hamming distance d(s, s_i) ≤ d for all s_y ∈ B.rnThe farthest string problem: given a group of strings g = {g_1, g_2, ..., g_(n2)}; with all strings of the same length L, and an integer d_b, the farthest string problem is to compute a center string s of length L such that the Hamming distance d(s,g_j) ≥ L - d_b for all g_j ∈g.rnThe distinguishing string selection problem: given two groups of strings B (bad genes) and g (good genes), B = {s_1, s_2,..., s_(n1)} and g = {g_(n1+1), g_(n1+2), ...,g_(n2)}, with all strings of the same length L, and two integers d_b and d_g with d_g ≥ L - d_b, the Distinguishing String Selection problem is to compute a center string s of length L such that the Hamming distance d(s, s_i) ≤ d_b, ∨s_i ∈ B and the Hamming distance d(s, g_j) ≥ d_g for all g_j ∈g.rnOur results: We design an O(Ln + nd(|∑ - 1|)~d2~(3.25d)) time fixed parameter algorithm for the closest string problem which improves upon the best known O(Ln + nd2~(4d) × (|∑| - 1)~d) algorithm in [14], where |∑| is the size of the alphabet. We also design fixed parameter algorithms for both the farthest string problem and the distinguishing string selection problem. Both algorithms run in time O(Ln + nd2~(3.25d)) when the input strings are binary strings over E = {0,1}.