Variants of constrained longest common subsequence

DOI10.1016/J.IPL.2010.07.015zbMATH Open1234.68472arXiv0912.0368OpenAlexW2038282261MaRDI QIDQ407588FDOQ407588

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)

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.

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

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

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)

Cites Work

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

Cited In (19)

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

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)