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

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;PIROLA, YURI
2010

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.
Articolo in rivista - Articolo scientifico
Algorithms, Longest common subsequence, Constrained longest common subsequence, Fixed-parameter tractability
English
877
881
5
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].
Bonizzoni, P; DELLA VEDOVA, G; Dondi, R; Pirola, Y
File in questo prodotto:
File Dimensione Formato  
journ-art-10-ipl.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 143.28 kB
Formato Adobe PDF
143.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/15251
Citazioni
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 25
Social impact