Variants of constrained longest common subsequence

DOI10.1016/J.IPL.2010.07.015MaRDI QIDQ407588zbMATH OpenOpenAlexFDO

Authors Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola

Publication date 27 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.0368

zbMATH Keywords

fixed-parameter tractabilitylongest common subsequenceconstrained longest common subsequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Abstract: In this work, 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, a set C_s of strings, and a function Co from A to N, the DC-LCS problem consists in 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 a in A is upper bounded by Co(a). 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: 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. Secondly, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings and the size of the alphabet A. 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.

Recommendations

• The constrained longest common subsequence problem
• scientific article; zbMATH DE number 6697960
• On the generalized constrained longest common subsequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Longest Common Subsequence with Gap Constraints
• On solving a generalized constrained longest common subsequence problem
• A fast algorithm of constrained longest common subsequence
• Algorithms for computing variants of the longest common subsequence problem
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Algorithms for Computing Variants of the Longest Common Subsequence Problem

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• A simple algorithm for the constrained sequence problems
• Color-coding
• Constrained LCS: Hardness and Approximation
• DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE
• Fast linear-space computations of longest common subsequences
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Introduction to algorithms
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Repetition-free longest common subsequence
• The Complexity of Some Problems on Subsequences and Supersequences
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(19)

• Approximability of constrained LCS
• Doubly-constrained LCS and hybrid-constrained LCS problems revisited
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• The constrained shortest common supersequence problem
• Fixed-parameter algorithms for scaffold filling
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Beam-ACO for the repetition-free longest common subsequence problem
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Approximability of constrained LCS
• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• Exemplar Longest Common Subsequence
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• The Constrained Longest Common Subsequence Problem for Degenerate Strings
• On the parameterized complexity of the repetition free longest common subsequence problem
• Constrained sequence analysis algorithms in computational biology
• Comparing incomplete sequences via longest common subsequence
• Longest common subsequence problem for unoriented and cyclic strings
• Repetition-free longest common subsequence of random sequences

This page was built for publication: Variants of constrained longest common subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407588)