In this paper, we define the reoptimization variant of the closest substring problem (CSP) under sequence addition. We show that, even with the additional information we have about the problem instance, the problem of finding a closest substring is still NP-hard. We investigate the combinatorial property of optimization problems called self-reducibility. We show that problems that are polynomial-time reducible to self-reducible problems also exhibits the same property. We illustrate this in the context of CSP. We used the property to show that although we cannot improve the approximability of the problem, we can improve the running time of the existing PTAS for CSP.
Due to the hardness results presented in @cite_12 , several other efforts were made to identify for which types of input instances the problem becomes easier to solve. A result in @cite_7 shows that even if the set of input instances is defined over the binary alphabet, we still cannot obtain a practical polynomial-time algorithm for small error bounds. Aside from characterizing input instances, one line of research focused on the of the problem @cite_18 . Based on these studies, it is shown that the problem is , i.e., fixing a parameter such as the pattern length or alphabet size will not make the problem easier to solve.
@cite_18 @cite_7 @cite_12
2148893137 2115667895
Many algorithms for motif finding that are commonly used in bioinformatics start by sampling r potential motif occurrences from n input sequences. The motif is derived from these samples and evaluated on all sequences. This approach works extremely well in practice, and is implemented by several programs. Li, Ma and Wang have shown that a simple algorithm of this sort is a polynomial-time approximation scheme. However, in 2005, we showed specific instances of the motif finding problem for which the approximation ratio of a slight variation of this scheme converges to one very slowly as a function of the sample size r, which seemingly contradicts the high performance of sample-based algorithms. Here, we account for the difference by showing that, for a variety of different definitions of “strong” binary motifs, the approximation ratio of sample-based algorithms converges to one exponentially fast in r. We also describe “very strong” motifs, for which the simple sample-based approach always identifies the correct motif, even for modest values of r. The longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as the number of sequences to be analyzed, the length of the common subsequence, and the size of the alphabet. Lower bounds on the complexity of this basic problem imply lower bounds on a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time ƒ(k) · nα where α is independent of k (termed fixed-parameter tractability). It can be argued that this is the appropriate asymptotic model of feasible computability for problems for which a small range of parameter values covers important applications — a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The longest common subsequence (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem parameterized both by the number of sequences and the length of the common subsequence, is complete for W[1]. All of the above results are obtained for unrestricted alphabet sizes. For alphabets of a fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard.