An improved algorithm for the longest common subsequence problem

DOI10.1016/J.COR.2011.02.026MaRDI QIDQ1762001zbMATHOpenAlexFDO

Authors Sayyed Rasoul Mousavi, Farzaneh Sadat Tabataba

Publication date 15 November 2012

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2011.02.026

zbMATH Keywords

algorithmsbioinformaticslongest common subsequencebeam searchLCSheuristic function

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Recommendations

• A hyper-heuristic for the longest common subsequence problem
• Beam search for the longest common subsequence problem
• On solving a generalized constrained longest common subsequence problem
• Publication:4862293
• Probabilistic Beam Search for the Longest Common Subsequence Problem

Cites work

• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A large neighborhood search heuristic for the longest common subsequence problem
• A linear space algorithm for computing maximal common subsequences
• A specialized branching and fathoming technique for the longest common subsequence problem
• Beam search for the longest common subsequence problem
• Computing a longest common subsequence for a set of strings
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Performance analysis of some simple heuristics for computing longest common subsequences
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• Sparse dynamic programming II
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(16)

• Improved approaches to solve the one-to-one skewgram problem
• A large neighborhood search heuristic for the longest common subsequence problem
• Beam search for the longest common subsequence problem
• A CGM Algorithm Solving the Longest Increasing Subsequence Problem
• An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters
• A specialized branching and fathoming technique for the longest common subsequence problem
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• A hyper-heuristic for the longest common subsequence problem
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• On the role of metaheuristic optimization in bioinformatics
• Anytime algorithms for the longest common palindromic subsequence problem
• Constrained sequence analysis algorithms in computational biology
• A diagonal-based algorithm for the longest common increasing subsequence problem
• A learning algorithm for the longest common subsequence problem
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• Deposition and extension approach to find longest common subsequence for thousands of long sequences

This page was built for publication: An improved algorithm for the longest common subsequence problem

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