EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The longest letter-duplicated subsequence and related problems

Wenfeng Lai, Adiesha Liyanage, Binhai Zhu, Peng Zou

Acta Informatica · 2024-09 · 61 (3) · 315-329

DOI: 10.1007/s00236-024-00459-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Acta Informatica, online erschienen am 20.07.2024. Verfasst von Wenfeng Lai und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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_1^{d_1}x_2^{d_2}\ldots x_k^{d_k}$$ x 1 d 1 x 2 d 2 … x k d k with $$x_i\in \Sigma $$ x i ∈ Σ , $$x_j\ne x_{j+1}$$ x j ≠ x j + 1 and $$d_i\ge 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 $$\Sigma $$ Σ 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_i^{d_i} (d_i\ge 2)$$ x i d i ( d i ≥ 2 ) could be any positive function which might not grow with $$d_i$$ d i . We give a non-trivial $$O(n^2)$$ O ( n 2 ) time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of S whose weight is maximized.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Lai, W., Liyanage, A., Zhu, B., & Zou, P. (2024). The longest letter-duplicated subsequence and related problems. Acta Informatica, 61(3), 315-329. https://doi.org/10.1007/s00236-024-00459-7

Vancouver

Lai W, Liyanage A, Zhu B, Zou P. The longest letter-duplicated subsequence and related problems. Acta Informatica. 2024;61(3):315-329. doi:10.1007/s00236-024-00459-7

BibTeX
@article{Lai2024,
  author = {Lai, Wenfeng and Liyanage, Adiesha and Zhu, Binhai and Zou, Peng},
  title = {The longest letter-duplicated subsequence and related problems},
  journal = {Acta Informatica},
  year = {2024},
  volume = {61},
  number = {3},
  pages = {315--329},
  doi = {10.1007/s00236-024-00459-7}
}
Kostenlos starten →