The longest letter-duplicated subsequence and related problems

Motivated by computing duplication patterns in sequences, a new problem called the longest letter-duplicated subsequence (LLDS) is proposed. Given a sequence S of length n , a letter-duplicated subsequence is a subsequence of S in the form of x₁d₁x₂d₂… xₖdₖ x 1 d 1 x 2 d 2 … x k d k with xᵢ∈ Σ x i ∈ Σ , xⱼ≠ xⱼ₊₁ x j ≠ x j + 1 and dᵢ≥ 2 d i ≥ 2 for all i in [ k ] and j in $$[k-1]$$ [ k - 1 ] . A linear time algorithm for computing a longest letter-duplicated subsequence (LLDS) of S can be easily obtained. In this paper, we focus on two variants of this problem: (1) ‘all-appearance’ version, i.e., all letters in Σ Σ must appear in the solution, and (2) the weighted version. For the former, we obtain dichotomous results: We prove that, when each letter appears in S at least 4 times, the problem and a relaxed version on feasibility testing (FT) are both NP-hard. The reduction is from (3⁺,1,2⁻) ( 3 + , 1 , 2 - ) -SAT, where all 3-clauses (i.e., containing 3 lals) are monotone (i.e., containing only positive literals) and all 2-clauses contain only negative literals. We then show that when each letter appears in S at most 3 times, then the problem admits an O ( n ) time algorithm. Finally, we consider the weighted version, where the weight of a block xᵢdᵢ (dᵢ≥ 2) x i d i ( d i ≥ 2 ) could be any positive function which might not grow with dᵢ d i . We give a non-trivial O(n²) O ( n 2 ) time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of S whose weight is maximized.