An improved algorithm for the longest common subsequence problem

DOI10.1016/J.COR.2011.02.026zbMath1251.90395OpenAlexW2084652256MaRDI QIDQ1762001

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

algorithmsbeam searchbioinformaticslongest common subsequenceLCSheuristic function

Mathematics Subject Classification ID

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

Related Items (6)

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters ⋮ Improved approaches to solve the one-to-one skewgram problem ⋮ On the role of metaheuristic optimization in bioinformatics ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Anytime algorithms for the longest common palindromic subsequence problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a longest common subsequence for a set of strings
• Beam search for the longest common subsequence problem
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• A large neighborhood search heuristic for the longest common subsequence problem
• Performance analysis of some simple heuristics for computing longest common subsequences
• A linear space algorithm for computing maximal common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Sparse dynamic programming II
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Probabilistic Beam Search for the Longest Common Subsequence Problem

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