On the Longest Common Rigid Subsequence Problem |
| |
Authors: | Nikhil Bansal Moshe Lewenstein Bin Ma Kaizhong Zhang |
| |
Affiliation: | 1. IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY, 10598, USA 2. Department of Computer Science, Bar Ilan University, Ramat Gan, 52900, Israel 3. Department of Computer Science, University of Western Ontario, London, ON, N6A 5B7, Canada
|
| |
Abstract: | The longest common subsequence problem (LCS) and the closest substring problem (CSP) are two models for finding common patterns
in strings, and have been studied extensively. Though both LCS and CSP are NP-Hard, they exhibit very different behavior with
respect to polynomial time approximation algorithms. While LCS is hard to approximate within n
δ
for some δ>0, CSP admits a polynomial time approximation scheme. In this paper, we study the longest common rigid subsequence problem
(LCRS). This problem shares similarity with both LCS and CSP and has an important application in motif finding in biological
sequences. We show that it is NP-hard to approximate LCRS within ratio n
δ
, for some constant δ>0, where n is the maximum string length. We also show that it is NP-Hard to approximate LCRS within ratio Ω(m), where m is the number of strings. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|