On the longest common rigid subsequence problem

N. Bansal, M. Lewenstein, B. Ma, Kaizhong Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)

    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 (delta) for some delta > 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 (delta) , for some constant delta > 0, where n is the maximum string length. We also show that it is NP-Hard to approximate LCRS within ratio Omega(m), where m is the number of strings.
    Original languageEnglish
    Pages (from-to)270-280
    JournalAlgorithmica
    Volume56
    Issue number2
    DOIs
    Publication statusPublished - 2010

    Fingerprint

    Dive into the research topics of 'On the longest common rigid subsequence problem'. Together they form a unique fingerprint.

    Cite this