An improved algorithm for the longest common subsequence problem

DOI10.1016/j.cor.2011.02.026zbMath1251.90395MaRDI 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

algorithms; beam search; bioinformatics; longest common subsequence; LCS; heuristic function

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

92D20: Protein sequences, DNA sequences

68W32: Algorithms on strings

Related Items

A hyper-heuristic for the longest common subsequence problem, Constrained sequence analysis algorithms in computational biology, An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters, 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