Approximability of constrained LCS

作者：Jiang Minghui^*

来源：Journal of Computer and System Sciences, 2012, 78(3): 689-697.

DOI：10.1016/j.jcss.2011.10.002

• Longest common subsequence
• Computational biology
• Computational complexity
• Approximation algorithms

The problem CONSTRAINED LONGEST COMMON SUBSEQUENCE is a natural extension to the classical problem LONGEST COMMON SUBSEQUENCE, and has important applications to bioinformatics. Given k input sequences A(1),..., A(k) and I constraint sequences B-1,..., B-1, C-LCS(k, l) is the problem of finding a longest common subsequence of A(1),..., A(k) that is also a common supersequence of B-1,..., B-1. Gotthilf et al. gave a polynomial-time algorithm that approximates C-LCS(k, 1) within a factor root(m) over cap vertical bar Sigma vertical bar, where (m) over cap is the length of the shortest input sequence and vertical bar Sigma vertical bar is the alphabet size. They asked whether there are better approximation algorithms and whether there exists a lower bound. In this paper, we answer their questions by showing that their approximation factor root(m) over cap vertical bar Sigma vertical bar is in fact already very close to optimal although a small improvement is still possible: %26lt;br%26gt;1. For any computable function f and any epsilon %26gt; 0, there is no polynomial-time algorithm that approximates C-LCS(k, 1) within a factor f(vertical bar E vertical bar) . (m) over cap (1/2-epsilon) unless NP = P. Moreover, this holds even if the constraint sequence is unary. %26lt;br%26gt;2. There is a polynomial-time randomized algorithm that approximates C-LCS(k, 1) within a factor vertical bar Sigma vertical bar . O(root OPT . loglogOPT/logOPT) with high probability, where OPT is the length of the optimal solution, OPT %26lt;= (m) over cap. %26lt;br%26gt;For the problem over an alphabet of arbitrary size, we show that %26lt;br%26gt;3. For any epsilon %26gt; 0, there is no polynomial-time algorithm that approximates C-LCS(k, 1) within a factor (m) over cap (1-epsilon) unless NP = P. %26lt;br%26gt;4. There is a polynomial-time-algorithm that approximates C-LCS(k, 1) within a factor O ((m) over cap /log (m) over cap). %26lt;br%26gt;We also present some complementary results on exact and parameterized algorithms for C-LCS(k, 1).

• 出版日期2012-5