We consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s1 and s2 over an alphabet Σ, a set Cs of strings, and a function Co:Σ→N, the DC-LCS problem consists of finding the longest subsequence s of s1 and s2 such that s is a supersequence of all the strings in Cs and such that the number of occurrences in s of each symbol σ∈Σ is upper bounded by Co(σ). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem that have been introduced previously in the literature: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution which is also applicable to the more specialized problems. Second, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings (|Cs|) and the size of the alphabet Σ. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant. © 2010 Elsevier B.V.

Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Pirola, Y. (2010). Variants of constrained longest common subsequence. INFORMATION PROCESSING LETTERS, 110(20), 877-881 [10.1016/j.ipl.2010.07.015].

### Variants of constrained longest common subsequence

#### Abstract

We consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s1 and s2 over an alphabet Σ, a set Cs of strings, and a function Co:Σ→N, the DC-LCS problem consists of finding the longest subsequence s of s1 and s2 such that s is a supersequence of all the strings in Cs and such that the number of occurrences in s of each symbol σ∈Σ is upper bounded by Co(σ). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem that have been introduced previously in the literature: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution which is also applicable to the more specialized problems. Second, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings (|Cs|) and the size of the alphabet Σ. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant. © 2010 Elsevier B.V.
##### Scheda breve Scheda completa Scheda completa (DC)
Articolo in rivista - Articolo scientifico
Algorithms, Longest common subsequence, Constrained longest common subsequence, Fixed-parameter tractability
English
2010
110
20
877
881
reserved
Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Pirola, Y. (2010). Variants of constrained longest common subsequence. INFORMATION PROCESSING LETTERS, 110(20), 877-881 [10.1016/j.ipl.2010.07.015].
File in questo prodotto:
File
journ-art-10-ipl.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 143.28 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/15251`