The longest subsequence-duplicated subsequence and related problems

Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-duplicated subsequence (LSDS) is proposed. Given a sequence S of length n, a subsequence-duplicated subsequence is a subsequence of S in the form of x 1 d 1 x 2 d 2 ⋯ x k d k with x i being a subsequence of S, x j ≠ x j + 1 and d i ≥ 2 for all i in [ k ] and j in [ k − 1 ]. We first present an O ( n 6 ) time algorithm to compute the longest cubic subsequences of all the O ( n 2 ) substrings of S, improving the trivial O ( n 7 ) bound. Then, an O ( n 6 ) time algorithm for computing the longest subsequence-duplicated subsequence (LSDS) of S is obtained. Finally we focus on two variants of this problem. We first consider the constrained version when Σ is unbounded, each letter appears in S at most d times and all the letters in Σ must appear in the solution. We show that the problem is NP-hard for d = 4, via a reduction from a special version of SAT (which is obtained from 3-COLORING). We then show that when each letter appears in S at most d = 3 times, then the problem is solvable in O ( n 4 ) time.

Authors

• Manuel Lafond
• Wenfeng Lai
• Adiesha Liyanage
• Binhai Zhu

Keywords

• Tandem duplications
• Longest common subsequence
• Longest letter-duplicated subsequence
• NP-completeness
• Dynamic programming