An Efficient Dynamic Programming Algorithm for the Generalized LCS Problem with Multiple Substring Exclusion Constrains

2013/03/08 by Lei Wang, Xiaodong Wang, Wang, Lei +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.DS

paper · pdf · doi:10.48550/arxiv.1303.1872

arXiv admin note: substantial text overlap with arXiv:1301.7183

arxiv created 2013/03/08 · openalex publication_date 2013/03/08 · arxiv updated 2013/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider a generalized longest common subsequence problem with multiple substring exclusion constrains. For the two input sequences X and Y of lengths n and m, and a set of d constrains P=\P₁,...,P_d\ of total length r, the problem is to find a common subsequence Z of X and Y excluding each of constrain string in P as a substring and the length of Z is maximized. The problem was declared to be NP-hard\cite1, but we finally found that this is not true. A new dynamic programming solution for this problem is presented in this paper. The correctness of the new algorithm is proved. The time complexity of our algorithm is O(nmr).

Citations

• Fast Pattern Matching in Strings
• A Dynamic Programming Solution to a Generalized LCS Problem

Cited by

• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints

Related

• A Dynamic Programming Solution to a Generalized LCS Problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints
• An Efficient Dynamic Programming Algorithm for STR-IC-SEQ-EC-LCS Problem
• Faster STR-EC-LCS Computation
• Efficient algorithms for the longest common subsequence in k-length substrings