Center and distinguisher for strings with unbounded alphabet
Consider two sets B and G of strings of length L with characters from an unbounded alphabet Sigma, i.e., the size of Sigma is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of B is a string that minimizes the maximum of Hamming(1) distance(s, s*) over all string s : s is an element of B. In contrast, a farthest string t* from G maximizes the minimum of Hamming distance(t*,t) over all elements t: t is an element of G. A distinguisher of B from G is a string that is close to every string in B and far away from any string in G. We obtain polynomial time approximation schemes to settle the above problems.
approximation algorithm computational molecular biology center string selection distinguishing string selection unbounded alphabet size