Back to Search
Start Over
Approximability of constrained LCS
- Source :
-
Journal of Computer & System Sciences . May2012, Vol. 78 Issue 3, p689-697. 9p. - Publication Year :
- 2012
-
Abstract
- Abstract: 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 and l constraint sequences , is the problem of finding a longest common subsequence of that is also a common supersequence of . Gotthilf et al. gave a polynomial-time algorithm that approximates within a factor , where is the length of the shortest input sequence and 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 is in fact already very close to optimal although a small improvement is still possible: [1.] For any computable function f and any , there is no polynomial-time algorithm that approximates within a factor unless . Moreover, this holds even if the constraint sequence is unary. [2.] There is a polynomial-time randomized algorithm that approximates within a factor with high probability, where OPT is the length of the optimal solution, . For the problem over an alphabet of arbitrary size, we show that [3.] For any , there is no polynomial-time algorithm that approximates within a factor unless . [4.] There is a polynomial-time algorithm that approximates within a factor . We also present some complementary results on exact and parameterized algorithms for . [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 78
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 73192152
- Full Text :
- https://doi.org/10.1016/j.jcss.2011.10.002