A simple algorithm for the constrained sequence problems

DOI10.1016/J.IPL.2004.02.008MaRDI QIDQ2390246zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 July 2009

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

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

zbMATH Keywords

constrained longest common subsequencesequence alignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39)

Abstract: In this paper we address the constrained longest common subsequence problem. Given two sequences $X$, $Y$ and a constrained sequence $P$, a sequence $Z$ is a constrained longest common subsequence for $X$ and $Y$ with respect to $P$ if $Z$ is the longest subsequence of $X$ and $Y$ such that $P$ is a subsequence of $Z$. Recently, Tsai cite{Tsai} proposed an $O(n^{2}cdot{m}^{2}cdotr)$ time algorithm to solve this problem using dynamic programming technique, where $n$, $m$ and $r$ are the lengths of $X$, $Y$ and $P$, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in $O(ncdotmcdotr)$ time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved.

Recommendations

• The constrained longest common subsequence problem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• A fast algorithm of constrained longest common subsequence
• scientific article; zbMATH DE number 6697960
• On the generalized constrained longest common subsequence problems

Cites work

• A faster algorithm computing string edit distances
• Algorithms for the Longest Common Subsequence Problem
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• The Complexity of Some Problems on Subsequences and Supersequences
• The constrained longest common subsequence problem
• The String-to-String Correction Problem

Cited in

(56)

• The constrained longest common subsequence problem
• Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
• Monge sequences and a simple assignment algorithm
• Sorting a permutation by best short swaps
• A data structure for substring-substring LCS length queries
• An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
• Tight conditional lower bounds for longest common increasing subsequence
• Maximal common subsequence algorithms
• Comparing incomplete sequences via longest common subsequence
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• Efficient algorithms for regular expression constrained sequence alignment
• Efficient algorithms for finding interleaving relationship between sequences
• RNA multiple structural alignment with longest common subsequences
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• A dynamic programming solution to a generalized LCS problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• Fast Algorithms for Local Similarity Queries in Two Sequences
• A fast algorithm of constrained longest common subsequence
• On the complexity of constrained sequences alignment problems
• Constrained pairwise and center-star sequences alignment problems
• Faster STR-EC-LCS computation
• An algorithm for the constrained heaviest common subsequence problem
• The Constrained Longest Common Subsequence Problem for Degenerate Strings
• Constrained LCS: Hardness and Approximation
• A geometric framework for solving subsequence problems in computational biology efficiently
• The constrained shortest common supersequence problem
• Variants of constrained longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• scientific article; zbMATH DE number 4123514 (Why is no real title available?)
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Approximability of constrained LCS
• A recurrent algorithm for solving a combinatorial problem of arrangement with restrictions
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• On the generalized constrained longest common subsequence problems
• Bit-parallel algorithm for the constrained longest common subsequence problem
• Tight conditional lower bounds for longest common increasing subsequence
• Maximal common subsequence algorithms
• Computing longest common square subsequences
• Bit-parallel algorithms for the merged longest common subsequence problem
• An algorithm and applications to sequence alignment with weighted constraints
• Constrained sequence analysis algorithms in computational biology
• A fast algorithm for the constrained multiple sequence alignment problem
• Implementation and Application of Automata
• Computational and Information Science
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Linear-space S-table algorithms for the longest common subsequence problem
• Space-efficient STR-IC-LCS computation
• Faster space-efficient STR-IC-LCS computation
• String editing under pattern constraints
• The generalized constrained longest common subsequence in the run-length encoded format
• Efficient algorithms for enumerating maximal common subsequences of two strings
• Regular expression constrained sequence alignment
• New efficient algorithms for the LCS and constrained LCS problems
• Finite automata based algorithms on subsequences and supersequences of degenerate strings

This page was built for publication: A simple algorithm for the constrained sequence problems

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